
// 获取一个K页的span
Span* PageCache::NewSpan(size_t k)
{
	assert(k > 0 && k < NPAGES);

	// 首先查看page cache中第K页的span是否为空
	if(!_spanLists[k].Empty())
	{
		return _spanLists[k].PopFront();
	}

	// 然后遍历page cache后面更大的页，如果存在，进行切分
	for(size_t i = k + 1; i < NPAGES; i++)
	{
		if(!_spanLists[i].Empty())
		{
			// 存在更大的页，进行切分，然后将剩余的span挂到对应的链表中
			Span* nSpan = _spanLists[i].PopFront();
			Span* kSpan = new Span;

			kSpan->_pageId = nSpan->_pageId;
			kSpan->_n += k;

			nSpan->_pageId += k;
			nSpan->_n -= k;

			_spanLists[nSpan->_n].PushFront(nSpan);

			return kSpan;
		}
	}

	// 走到这说明page cache已经没有更大页的span了，此时只能直接向系统堆申请128页的span
	Span* bigSpan = new Span;
	void* ptr = SystemAlloc(NPAGES - 1);

	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
	bigSpan->_n = NPAGES - 1;

	_spanLists[bigSpan->_n].PushFront(bigSpan);

	return NewSpan(k);
}


#include "PageCache.h"


// 类中的静态成员变量在.cpp文件中定义
PageCache PageCache::_sInst;


// // 获取一个K页的span
// Span* PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NPAGES);

// 	// 先检查第k个桶里面有没有span
// 	if (!_spanLists[k].Empty())
// 	{
// 		return _spanLists->PopFront();
// 	}

// 	// 检查一下后面的桶里面有没有span，如果有可以把他它进行切分
// 	for (size_t i = k+1; i < NPAGES; ++i)
// 	{
// 		if (!_spanLists[i].Empty())
// 		{
// 			Span* nSpan = _spanLists[i].PopFront();
// 			Span* kSpan = new Span;

// 			// 在nSpan的头部切一个k页下来
// 			// k页span返回
// 			// nSpan再挂到对应映射的位置
// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n = k;

// 			nSpan->_pageId += k;
// 			nSpan->_n -= k;

// 			_spanLists[nSpan->_n].PushFront(nSpan);

// 			return kSpan;
// 		}
// 	}

// 	// 走到这个位置就说明后面没有大页的span了
// 	// 这时就去找堆要一个128页的span
// 	Span* bigSpan = new Span;
// 	void* ptr = SystemAlloc(NPAGES - 1);
// 	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
// 	bigSpan->_n = NPAGES - 1;

// 	_spanLists[bigSpan->_n].PushFront(bigSpan);

// 	return NewSpan(k);
// }



// // 获取一个K页的span
// Span* PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NPAGES);

// 	// 首先查看page cache中第K页的span是否为空
// 	if(!_spanLists[k].Empty())
// 	{
// 		return _spanLists[k].PopFront();
// 	}

// 	// 走到这说明需要遍历page cache找更大的页，然后切开
// 	for(size_t i = k + 1; i < NPAGES; i++)
// 	{
// 		if(!_spanLists[i].Empty())
// 		{
// 			Span* nSpan = _spanLists[i].PopFront();
// 			Span* kSpan = new Span;

// 			// 将n页的span切开，一部分给kSpan, 一部分插入到对应的链表中
// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n += k;

// 			nSpan->_pageId += k;
// 			nSpan->_n -= k;

// 			_spanLists[nSpan->_n].PushFront(nSpan);

// 			return kSpan;
// 		}
// 	}

// 	// 走到这说明后面也没有更大的页了，需要从系统堆中直接申请128页的span
// 	Span* bigSpan = new Span;
// 	void* ptr = SystemAlloc(NPAGES - 1);
// 	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
// 	bigSpan->_n = NPAGES - 1;

// 	_spanLists[bigSpan->_n].PushFront(bigSpan);

// 	return NewSpan(k);
// }


// // 获取一个K页的span
// Span* PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NPAGES);

// 	// 首先查看page cache中第K页的span是否为空
// 	if(!_spanLists[k].Empty())
// 	{
// 		return _spanLists[k].PopFront();
// 	}

// 	// 然后遍历page cache后面更大的页，如果存在，进行切分
// 	for(size_t i = k + 1; i < NPAGES; i++)
// 	{
// 		if(!_spanLists[i].Empty())
// 		{
// 			// 存在更大的页，进行切分，然后将剩余的span挂到对应的链表中
// 			Span* nSpan = _spanLists[i].PopFront();
// 			Span* kSpan = new Span;

// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n += k;

// 			nSpan->_pageId += k;
// 			nSpan->_n -= k;

// 			_spanLists[nSpan->_n].PushFront(nSpan);

// 			return kSpan;
// 		}
// 	}

// 	// 走到这说明page cache已经没有更大页的span了，此时只能直接向系统堆申请128页的span
// 	Span* bigSpan = new Span;
// 	void* ptr = SystemAlloc(NPAGES - 1);

// 	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
// 	bigSpan->_n = NPAGES - 1;

// 	_spanLists[bigSpan->_n].PushFront(bigSpan);

// 	return NewSpan(k);
// }


// 获取一个K页的span
Span* PageCache::NewSpan(size_t k)
{
	assert(k > 0 && k < NPAGES);

	// 首先查看当前的链表中是否存在非空的span
	if(!_spanLists[k].Empty())
	{
		return _spanLists[k].PopFront();
	}

	// 走到这说明需要遍历page cache，看是否有更大页的span

	for(size_t i = k + 1; i < NPAGES; i++)
	{
		if(!_spanLists[i].Empty())
		{
			Span* nSpan = _spanLists[i].PopFront();
			Span* kSpan = new Span;

			kSpan->_pageId = nSpan->_pageId;
			kSpan->_n = k;

			nSpan->_pageId += k;
			nSpan->_n -= k;

			_spanLists[nSpan->_n].PushFront(nSpan);

			return kSpan;
		}
	}

	// 走到这说明page cache后面也没有更大页的span了，需要直接向系统堆申请128页span
	Span* bigSpan = new Span;
	void* ptr = SystemAlloc(NPAGES - 1);

	bigSpan->_pageId = (PAGE_ID)(ptr) >> PAGE_SHIFT;
	bigSpan->_n = NPAGES - 1;

	_spanLists[bigSpan->_n].PushFront(bigSpan);

	return NewSpan(k);
}



void PageCache::ReleaseSpanToPageCache(Span* span)
{
	assert(span);

	// 对span前后的页进行合并，缓解内存碎片的问题
	while(1)
	{
		PAGE_ID prevId = span->_pageId - 1;
		auto ret = _idSpanMap.find(prevId);

		// 前面的页没有了，不合并了
		if(ret == _idSpanMap.end())
		{
			break;
		}

		// 前面的也正在使用，不合并了
		Span* prevSpan = ret->second;
		if(prevSpan->_isUse == true)
		{
			break;
		}

		// 合并出的页超过了NPAGES-1，不合并了
		if(span->_n + prevSpan->_n > NAPGES - 1)
		{
			break;
		}

		span->_pageId = prevSpan->_pageId;
		span->_n += prevSpan->_n;

		_spanLists[prevSpan->_n].Erase(prevSpan);
		delete prevSpan;
	}

	// 向后合并
	while(1)
	{
		PAGE_ID nextId = span->_pageId + span->_n;
		auto ret = _idSpanMap.find(nextId);

		// 后面的页没有了，不合并了
		if(ret == _idSpanMap.end())
		{
			break;
		}

		// 后面的页被使用了，不合并了
		Span* nextSpan = ret->second;
		if(nextSpan->_isUse == true)
		{
			break;
		}

		// 合并出了大于NPAGES-1的页，不合并了
		if(span->_n + nextSpan->_n > NPAGES - 1)
		{
			break;
		}

		span->_n += nextSpan->_n;

		_spanLists[nextSpan->_n].Erase(nextSpan);
		delete nextSpan;
	}

	_spanLists[span->_n].PushFront(span);
	span->_isUse = true;
	_idSpanMap[span->_pageId] = span;
	_idSpanMap[span->_pageId + span->_n - 1] = span; 
}



// 获取一个K页的span
Span* PageCache::NewSpan(size_t k)
{
	assert(k > 0 && k < NPAGES);

	// 首先查看该链表中是否有非空的span
	if(!_spanLists[k].Empty())
	{
		return _spanLists[k].PopFront();
	}

	// 走到这说明需要遍历page cache，找更大页的span，然后切分
	for(size_t i = k + 1; i < NPAGES; i++)
	{
		if(!_spanLists[i].Empty())
		{
			Span* nSpan = _spanLists[i].PopFront();
			Span* kSpan = new Span;

			kSpan->_pageId = nSpan->_pageId;
			kSpan->_n = k;

			nSpan->_pageId += k;
			nSpan->_n -= k;

			_spanLists[nSpan->_n].PushFront(nSpan);

			// 记录首尾页号到span的映射，方便page cache合并成更大页的span
			_idSpanMap[nSpan->_pageId] = nSpan;
			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

			// 记录页号到span的映射，方便释放内存时找到对应的span
			for(size_t i = 0; i < kSpan->_n; i++)
			{
				_idSpanMap[kSpan->_pageId + i] = kSpan;
			}

			return kSpan;
		}
	}

	// 走到这说明需要从page cache中申请内存
	void* ptr = SystemAlloc(NPAGES - 1);
	Span* bigSpan = new Span;

	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
	bigSpan->_n = NPAGES - 1;

	_spanLists[bigSpan->_n].PushFront(bigSpan);

	return NewSpan(k);
}

Span* PageCache::MapObjToSpan(void* obj)
{
	assert(obj);

	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;
	auto ret = _idSpanMap.find(id);

	if(ret == _idSpanMap.end())
	{
		assert(false);
		return nullptr;
	}
	else
	{
		return ret->second;
	}
}


void PageCache::ReleaseSpanToPageCache(Span* span)
{
	assert(span);

	// 合并前后页的span组成更大页的span，尽量减少内存碎片
	// 向前合并
	while(1)
	{
		PAGE_ID prevId = span->_pageId - 1;
		auto ret = _idSpanMap.find(prevId);

		// 前一页的span不存在，不合并了
		if(ret == _idSpanMap.end())
		{
			break;
		}

		// 前一页的span正在使用，不合并了
		Span* prevSpan = ret->second;
		if(prevSpan->_isUse == true)
		{
			break;
		}

		// 合并出了更大页的span，不合并了
		if(span->_n + prevSpan->_n > NPAGES - 1)
		{
			break;
		}

		span->_pageId = prevSpan->_pageId;
		span->_n += prevSpan->_n;

		_spanLists[prevSpan->_n].Erase(prevSpan);
		delete prevSpan;
	}

	// 向后合并
	while(1)
	{
		PAGE_ID nextId = span->_pageId + span->_n;
		auto ret = _idSpanMap.find(nextId);

		// 后一页的span不存在，不合并了
		if(ret == _idSpanMap.end())
		{
			break;
		}

		// 后一页的span正在被使用，不合并了
		Span* nextSpan = ret->second;
		if(nextSpan->_isUse == true)
		{
			break;
		}

		// 合并出了超过NPAGES-1页的span，不合并了
		if(span->_n + nextSpan->_n > NPAGES - 1)
		{
			break;
		}

		span->_n += nextSpan->_n;

		_spanLists[nextSpan->_n].Erase(nextSpan);
		delete nextSpan;
	}

	_spanLists[span->_n].PushFront(span);
	span->_isUse = false;

	_idSpanMap[span->_pageId] = span;
	_idSpanMap[span->_pageId + span->_n - 1] = span;
}



void* ThreadCache::Allocate(size_t size)
{
    assert(size <= MAX_BYTES);

    size_t alignSize = SizeClass::RoundUp(size);
    size_t index = SizeClass::Index(size);

    if(!_freeLists[index].Empty())
    {
        return _freeLists[index].Pop();
    }
    else
    {
        return ThreadCache::FetchFromCentralCache(index, alignSize);
    }
}


void ThreadCache::Deallocate(void* obj, size_t size)
{   
    assert(obj);
    assert(size <= MAX_BYTES);

    size_t index = SizeClass::Index(size);
    _freeLists[index].Push(obj);

    if(_freeLists[index].Size() >= _freeLists[index].MaxSize())
    {
        ThreadCache::ListTooLong(_freeLists[index], size);
    }
}


void* ThreadCache::FetchFromCentralCache(size_t index, size_t size)
{
    assert(size <= MAX_BYTES);

    // 慢开始反馈调节算法
    // 1.最开始不会一次批量申请太多，可能用不完浪费
    // 2.如果不断有size大小的内存需求，batchNum就会不断变大，直至上限
    // 3.小对象一次批量申请的上限值高
    // 4.大对象一次批量申请的上限值低
    size_t batchNum = std::min(_freeLists[index].MaxSize(), SizeClass::NumMoveSize(size));

    if(batchNum == _freeLists[index].MaxSize())
    {
        _freeLists[index].MaxSize() += 1;
    }

    void* start = nullptr;
    void* end = nullptr;
    size_t actualNum = CentralCache::GetInstance()->FetchRangeObj(start, end, batchNum, size);
    assert(actualNum > 0);

    if(actualNum == 1)
    {
        assert(start == end);
        return start;
    }
    else
    {
        _freeLists[index].PushRange(NextObj(start), end, actualNum - 1);
        return start;
    }
}


void ThreadCache::ListTooLong(FreeList& list, size_t size)
{
    assert(size <= MAX_BYTES);

    void* start = nullptr;
    void* end = nullptr;

    list.PopRange(start, end, list.MaxSize());

    CentralCache::GetInstance()->ReleaseListToSpan(start, size);
}


#include "PageCache.h"

// 类中的静态成员变量在.cpp文件中定义
PageCache PageCache::_sInst;

// // 获取一个K页的span
// Span* PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NPAGES);

// 	// 先检查第k个桶里面有没有span
// 	if (!_spanLists[k].Empty())
// 	{
// 		return _spanLists->PopFront();
// 	}

// 	// 检查一下后面的桶里面有没有span，如果有可以把他它进行切分
// 	for (size_t i = k+1; i < NPAGES; ++i)
// 	{
// 		if (!_spanLists[i].Empty())
// 		{
// 			Span* nSpan = _spanLists[i].PopFront();
// 			Span* kSpan = new Span;

// 			// 在nSpan的头部切一个k页下来
// 			// k页span返回
// 			// nSpan再挂到对应映射的位置
// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n = k;

// 			nSpan->_pageId += k;
// 			nSpan->_n -= k;

// 			_spanLists[nSpan->_n].PushFront(nSpan);

// 			return kSpan;
// 		}
// 	}

// 	// 走到这个位置就说明后面没有大页的span了
// 	// 这时就去找堆要一个128页的span
// 	Span* bigSpan = new Span;
// 	void* ptr = SystemAlloc(NPAGES - 1);
// 	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
// 	bigSpan->_n = NPAGES - 1;

// 	_spanLists[bigSpan->_n].PushFront(bigSpan);

// 	return NewSpan(k);
// }

// // 获取一个K页的span
// Span* PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NPAGES);

// 	// 首先查看page cache中第K页的span是否为空
// 	if(!_spanLists[k].Empty())
// 	{
// 		return _spanLists[k].PopFront();
// 	}

// 	// 走到这说明需要遍历page cache找更大的页，然后切开
// 	for(size_t i = k + 1; i < NPAGES; i++)
// 	{
// 		if(!_spanLists[i].Empty())
// 		{
// 			Span* nSpan = _spanLists[i].PopFront();
// 			Span* kSpan = new Span;

// 			// 将n页的span切开，一部分给kSpan, 一部分插入到对应的链表中
// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n += k;

// 			nSpan->_pageId += k;
// 			nSpan->_n -= k;

// 			_spanLists[nSpan->_n].PushFront(nSpan);

// 			return kSpan;
// 		}
// 	}

// 	// 走到这说明后面也没有更大的页了，需要从系统堆中直接申请128页的span
// 	Span* bigSpan = new Span;
// 	void* ptr = SystemAlloc(NPAGES - 1);
// 	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
// 	bigSpan->_n = NPAGES - 1;

// 	_spanLists[bigSpan->_n].PushFront(bigSpan);

// 	return NewSpan(k);
// }

// // 获取一个K页的span
// Span* PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NPAGES);

// 	// 首先查看page cache中第K页的span是否为空
// 	if(!_spanLists[k].Empty())
// 	{
// 		return _spanLists[k].PopFront();
// 	}

// 	// 然后遍历page cache后面更大的页，如果存在，进行切分
// 	for(size_t i = k + 1; i < NPAGES; i++)
// 	{
// 		if(!_spanLists[i].Empty())
// 		{
// 			// 存在更大的页，进行切分，然后将剩余的span挂到对应的链表中
// 			Span* nSpan = _spanLists[i].PopFront();
// 			Span* kSpan = new Span;

// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n += k;

// 			nSpan->_pageId += k;
// 			nSpan->_n -= k;

// 			_spanLists[nSpan->_n].PushFront(nSpan);

// 			return kSpan;
// 		}
// 	}

// 	// 走到这说明page cache已经没有更大页的span了，此时只能直接向系统堆申请128页的span
// 	Span* bigSpan = new Span;
// 	void* ptr = SystemAlloc(NPAGES - 1);

// 	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
// 	bigSpan->_n = NPAGES - 1;

// 	_spanLists[bigSpan->_n].PushFront(bigSpan);

// 	return NewSpan(k);
// }

// // 获取一个K页的span
// Span* PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NPAGES);

// 	// 首先查看当前的链表中是否存在非空的span
// 	if(!_spanLists[k].Empty())
// 	{
// 		return _spanLists[k].PopFront();
// 	}

// 	// 走到这说明需要遍历page cache，看是否有更大页的span

// 	for(size_t i = k + 1; i < NPAGES; i++)
// 	{
// 		if(!_spanLists[i].Empty())
// 		{
// 			Span* nSpan = _spanLists[i].PopFront();
// 			Span* kSpan = new Span;

// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n = k;

// 			nSpan->_pageId += k;
// 			nSpan->_n -= k;

// 			_spanLists[nSpan->_n].PushFront(nSpan);

// 			return kSpan;
// 		}
// 	}

// 	// 走到这说明page cache后面也没有更大页的span了，需要直接向系统堆申请128页span
// 	Span* bigSpan = new Span;
// 	void* ptr = SystemAlloc(NPAGES - 1);

// 	bigSpan->_pageId = (PAGE_ID)(ptr) >> PAGE_SHIFT;
// 	bigSpan->_n = NPAGES - 1;

// 	_spanLists[bigSpan->_n].PushFront(bigSpan);

// 	return NewSpan(k);
// }

// // 获取一个K页的span
// Span *PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NPAGES);

// 	// 查看当前的SpanList是否为空
// 	if (!_spanLists[k].Empty())
// 	{
// 		return _spanLists[k].PopFront();
// 	}

// 	// 走到这说明需要遍历page cache查看是否存在更大的页
// 	for (size_t i = k + 1; i < NPAGES; i++)
// 	{
// 		if (!_spanLists[i].Empty())
// 		{
// 			Span *nSpan = _spanLists[i].PopFront();
// 			Span *kSpan = new Span;

// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n = k;

// 			nSpan->_pageId += k;
// 			nSpan->_n -= k;

// 			_spanLists[nSpan->_n].PushFront(nSpan);

// 			// 存储nSpan的首位及末尾的页号跟nSpan的映射，方便page cache回收内存时进行合并查找
// 			_idSpanMap[nSpan->_pageId] = nSpan;
// 			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

// 			// 建立id与span的映射，方便central cache回收小块内存时查找对应的span
// 			for(size_t i = 0; i < nSpan->_n; i++)
// 			{
// 				_idSpanMap[kSpan->_pageId + i] = kSpan;
// 			}

// 			return kSpan;
// 		}
// 	}

// 	// 走到这说明需要从系统堆中申请128页的span
// 	void *ptr = SystemAlloc(NPAGES - 1);
// 	Span *bigSpan = new Span;

// 	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
// 	bigSpan->_n = NAGES - 1;

// 	_spanLists[bigSpan->_n].PushFront(bigSpan);

// 	return NewSpan(k);
// }



// Span* PageCache::MapObjToSpan(void* obj)
// {
// 	assert(obj);

// 	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;
// 	auto ret = _idSpanMap.find(id);

// 	if(ret != _idSpanMap.end())
// 	{
// 		return ret->second;
// 	}
// 	else
// 	{
// 		assert(false);
// 		return nullptr;
// 	}
// }


// // void PageCache::ReleaseSpanToPageCache(Span* span)
// // {
// // 	// 对span前后的页，尝试进行合并，缓解内存碎片问题
// // 	while (1)
// // 	{
// // 		PAGE_ID prevId = span->_pageId - 1;
// // 		auto ret = _idSpanMap.find(prevId);
// // 		// 前面的页号没有，不合并了
// // 		if (ret == _idSpanMap.end())
// // 		{
// // 			break;
// // 		}

// // 		// 前面相邻页的span在使用，不合并了
// // 		Span* prevSpan = ret->second;
// // 		if (prevSpan->_isUse == true)
// // 		{
// // 			break;
// // 		}

// // 		// 合并出超过128页的span没办法管理，不合并了
// // 		if (prevSpan->_n + span->_n > NPAGES-1)
// // 		{
// // 			break;
// // 		}

// // 		span->_pageId = prevSpan->_pageId;
// // 		span->_n += prevSpan->_n;

// // 		_spanLists[prevSpan->_n].Erase(prevSpan);
// // 		delete prevSpan;
// // 	}

// // 	// 向后合并
// // 	while (1)
// // 	{
// // 		PAGE_ID nextId = span->_pageId + span->_n;
// // 		auto ret = _idSpanMap.find(nextId);
// // 		if (ret == _idSpanMap.end())
// // 		{
// // 			break;
// // 		}

// // 		Span* nextSpan = ret->second;
// // 		if (nextSpan->_isUse == true)
// // 		{
// // 			break;
// // 		}

// // 		if (nextSpan->_n + span->_n > NPAGES-1)
// // 		{
// // 			break;
// // 		}

// // 		span->_n += nextSpan->_n;

// // 		_spanLists[nextSpan->_n].Erase(nextSpan);
// // 		delete nextSpan;
// // 	}

// // 	_spanLists[span->_n].PushFront(span);
// // 	span->_isUse = false;
// // 	_idSpanMap[span->_pageId] = span;
// // 	_idSpanMap[span->_pageId+span->_n-1] = span;
// // }


// // void PageCache::ReleaseSpanToPageCache(Span* span)
// // {
// // 	assert(span);

// // 	// 对span前后的页进行合并，缓解内存碎片的问题
// // 	while(1)
// // 	{
// // 		PAGE_ID prevId = span->_pageId - 1;
// // 		auto ret = _idSpanMap.find(prevId);

// // 		// 前面的页没有了，不合并了
// // 		if(ret == _idSpanMap.end())
// // 		{
// // 			break;
// // 		}

// // 		// 前面的也正在使用，不合并了
// // 		Span* prevSpan = ret->second;
// // 		if(prevSpan->_isUse == true)
// // 		{
// // 			break;
// // 		}

// // 		// 合并出的页超过了NPAGES-1，不合并了
// // 		if(span->_n + prevSpan->_n > NAPGES - 1)
// // 		{
// // 			break;
// // 		}

// // 		span->_pageId = prevSpan->_pageId;
// // 		span->_n += prevSpan->_n;

// // 		_spanLists[prevSpan->_n].Erase(prevSpan);
// // 		delete prevSpan;
// // 	}

// // 	// 向后合并
// // 	while(1)
// // 	{
// // 		PAGE_ID nextId = span->_pageId + span->_n;
// // 		auto ret = _idSpanMap.find(nextId);

// // 		// 后面的页没有了，不合并了
// // 		if(ret == _idSpanMap.end())
// // 		{
// // 			break;
// // 		}

// // 		// 后面的页被使用了，不合并了
// // 		Span* nextSpan = ret->second;
// // 		if(nextSpan->_isUse == true)
// // 		{
// // 			break;
// // 		}

// // 		// 合并出了大于NPAGES-1的页，不合并了
// // 		if(span->_n + nextSpan->_n > NPAGES - 1)
// // 		{
// // 			break;
// // 		}

// // 		span->_n += nextSpan->_n;

// // 		_spanLists[nextSpan->_n].Erase(nextSpan);
// // 		delete nextSpan;
// // 	}

// // 	_spanLists[span->_n].PushFront(span);
// // 	span->_isUse = false;
// // 	_idSpanMap[span->_pageId] = span;
// // 	_idSpanMap[span->_pageId + span->_n - 1] = span; 
// // }


// // void PageCache::ReleaseSpanToPageCache(Span* span)
// // {
// // 	assert(span);

// // 	// 合并前后页的span，减少内存碎片的浪费
// // 	while(1)
// // 	{
// // 		PAGE_ID prevId = span->_pageId - 1;
// // 		auto ret = _idSpanMap.find(prevId);

// // 		// 前面的span不存在，不用合并
// // 		if(ret == _idSpanMap.end())
// // 		{
// // 			break;
// // 		}

// // 		// 前面的span被使用了，不合并了
// // 		Span* prevSpan = span->_prev;
// // 		if(prevSpan->_isUse == true)
// // 		{
// // 			break;
// // 		}

// // 		// 合并出的span超过了NPAGES-1页，不合并了
// // 		if(span->_n + prevSpan->_n > NPAGES - 1)
// // 		{
// // 			break;
// // 		}

// // 		span->_pageId = prevSpan->_pageId;
// // 		span->_n += prevSpan->_n;

// // 		_spanLists[prevSpan->_n].Erase(prevSpan);
// // 		delete prevSpan;
// // 	}

// // 	// 向后合并
// // 	while(1)
// // 	{
// // 		PAGE_ID nextId = span->_pageId;
// // 		auto ret = _idSpanMap.find(nextId);

// // 		// 后面的页不存在，不合并了
// // 		if(ret == _idSpanMap.end())
// // 		{
// // 			break;
// // 		}

// // 		// 后面的页被使用了，不合并了
// // 		Span* nextSpan = ret->second;
// // 		if(nextSpan->_isUse == true)
// // 		{
// // 			break;
// // 		}

// // 		// 合并出了超过NPAGES-1的span，不合并了
// // 		if(span->_n + nextSpan->_n > NPAGES - 1)
// // 		{
// // 			break;
// // 		}

// // 		span->_n += nextSpan->_n;

// // 		_spanLists[nextSpan->_n].Erase(nextSpan);
// // 		delete nextSpan;
// // 	}

// // 	_spanLists[span->_n].PushFront(span);
// // 	span->_isUse = false;
// // 	_idSpanMap[span->_pageId] = span;
// // 	_idSpanMap[span->_pageId + span->_n - 1] = span;
// // }


// void PageCache::ReleaseSpanToPageCache(Span* span)
// {
// 	assert(span);

// 	// 尝试合并前后页的span，减少内存碎片的浪费
// 	while(1)
// 	{
// 		PAGE_ID prevId = span->_pageId - 1;
// 		auto ret = _idSpanMap.find(prevId);

// 		// 前面页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 前面页的span正在被使用，不合并了
// 		Span* prevSpan = ret->second;
// 		if(prevSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1的span，不合并了
// 		if(span->_n + prevSpan->_n > NPAGES -1)
// 		{
// 			break;
// 		}

// 		span->_pageId = prevSpan->_pageId;
// 		span->_n += prevSpan->_n;

// 		_spanLists[prevSpan->_n].Erase(prevSpan);
// 		delete prevSpan;
// 	}

// 	// 向后合并
// 	while(1)
// 	{
// 		PAGE_ID nextId = span->_pageId + span->_n;
// 		auto ret = _idSpanMap.find(nextId);

// 		// 后一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 后一页的span正在被使用，不合并了
// 		Span* nextSpan = ret->second;
// 		if(nextSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1页的span，不合并了
// 		if(span->_n + nextSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_n += nextSpan->_n;

// 		_spanLists[nextSpan->_n].Erase(nextSpan);
// 		delete nextSpan;
// 	}

// 	_spanLists[span->_n].PushFront(span);
// 	span->_isUse = false;
// 	_idSpanMap[span->_pageId] = span;
// 	_idSpanMap[span->_pageId + span->_n - 1] = span;
// }


// // 获取一个K页的span
// Span* PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NPAGES);

// 	// 首先查看当前桶中是否有非空的span
// 	if(!_spanLists[k].Empty())
// 	{
// 		return _spanLists[k].PopFront();
// 	}

// 	// 走到这说明需要去遍历page cache找更大的桶
// 	for(size_t i = k + 1; i < NPAGES; i++)
// 	{
// 		if(!_spanLists[i].Empty())
// 		{
// 			Span* nSpan = _spanLists[i].PopFront();
// 			Span* kSpan = new Span;

// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n = k;

// 			nSpan->_pageId += k;
// 			nSpan->_n -= k;

// 			_spanLists[nSpan->_n].PushFront(nSpan);

// 			// 建立首尾页号到span的映射, 方便page cache进行前后页的合并
// 			_idSpanMap[nSpan->_pageId] = nSpan;
// 			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

// 			// 建立页号到span的映射，方便central cache回收小块内存时根据页号找到对应的span
// 			for(size_t i = 0; i < nSpan->_n; i++)
// 			{
// 				_idSpanMap[nSpan->_pageId + i] = nSpan;
// 			}

// 			return kSpan;
// 		}
// 	}

// 	// 走到这说明需要直接向堆申请内存
// 	Span* bigSpan = new Span;
// 	void* ptr = SystemAlloc(NPAGES - 1);

// 	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
// 	bigSpan->_n = NPAGES - 1;

// 	_spanLists[bigSpan->_n].PushFront(bigSpan);

// 	return PageCache::GetInstance()->NewSpan(k);
// }


// // 建立对象到span的映射
// Span* PageCache::MapObjToSpan(void* obj)
// {
// 	assert(obj);

// 	PAGE_ID pageId = (PAGE_ID)obj >> PAGE_SHIFT;
// 	auto ret = _idSpanMap.find(pageId);

// 	if(ret == _idSpanMap.end())
// 	{
// 		return ret->second;
// 	}
// 	else
// 	{
// 		assert(false);
// 		return nullptr;
// 	}
// }


// void PageCache::ReleaseSpanToPageCache(Span* span)
// {
// 	assert(span);

// 	// 合并前后页的span，尝试合并出更大页的span，减少内存碎片
// 	// 向前合并
// 	while(1)
// 	{
// 		PAGE_ID prevId = span->_pageId - 1;
// 		auto ret = _idSpanMap.find(prevId);

// 		// 前一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 前一页的span正在使用，不合并了
// 		Span* prevSpan = ret->second;
// 		if(prevSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出来的span超过了NPAGES-1
// 		if(span->_n + prevSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_pageId = prevSpan->_pageId;
// 		span->_n += prevSpan->_n;

// 		_spanLists[prevSpan->_n].Erase(prevSpan);
// 		delete prevSpan;
// 	}

// 	// 向后合并
// 	while(1)
// 	{
// 		PAGE_ID nextId = span->_pageId + span->_n;
// 		auto ret = _idSpanMap.find(nextId);

// 		// 下一页span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		Span* nextSpan = ret->second;
// 		// 下一页的span正在被使用，不合并了
// 		if(nextSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并后的span大于NPAGES-1，不合并了
// 		if(span->_n + nextSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_n += nextSpan->_n;

// 		_spanLists[nextSpan->_n].Erase(nextSpan);
// 		delete nextSpan;
// 	}

// 	_spanLists[span->_n].PushFront(span);
// 	span->_isUse = true;
// 	_idSpanMap[span->_pageId] = span;
// 	_idSpanMap[span->_pageId + span->_n - 1] = span;
// }


// // 获取一个K页的span
// Span* PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NPAGES);

// 	// 首先检查是否存在该span
// 	if(!_spanLists[k].Empty())
// 	{
// 		return _spanLists[k].PopFront();
// 	}

// 	// 走到这说明需要遍历page cache，找更大的span然后切分
// 	for(size_t i = k + 1; i < NPAGES; i++)
// 	{
// 		if(!_spanLists[i].Empty())
// 		{
// 			Span* nSpan = _spanLists[i].PopFront();
// 			Span* kSpan = new Span;

// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n = k;

// 			nSpan->_pageId += k;
// 			nSpan->_n -= k;

// 			_spanLists[nSpan->_n].PushFront(nSpan);

// 			// 记录切分后的span的首尾页号, 方便page cache合并成为更大页的span
// 			_idSpanMap[nSpan->_pageId] = nSpan;
// 			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

// 			// 记录页号到span的映射，方便central cache释放内存回来找到对应的span
// 			for(size_t i = 0; i < kSpan->_n; i++)
// 			{
// 				_idSpanMap[kSpan->_pageId + i] = kSpan;
// 			}

// 			return kSpan;
// 		}
// 	}

// 	// 走到这说明需要向系统堆中去申请大页的span - 128页
// 	void* ptr = SystemAlloc(NPAGES - 1);
// 	Span* bigSpan = new Span;

// 	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
// 	bigSpan->_n = NPAGES - 1;

// 	_spanLists[bigSpan->_n].PushFront(bigSpan);

// 	return PageCache::GetInstance()->NewSpan(k);
// }


// // 建立对象到span的映射
// Span* PageCache::MapObjToSpan(void* obj)
// {
// 	assert(obj);

// 	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;
// 	auto ret = _idSpanMap.find(id);

// 	if(ret == _idSpanMap.end())
// 	{
// 		assert(false);
// 		return nullptr;
// 	}
// 	else
// 	{
// 		return ret->second;
// 	}
// }




// void PageCache::ReleaseSpanToPageCache(Span* span)
// {
// 	assert(span);

// 	// 进行前后页的合并，合并成更大页的span，进而减少内存碎片
// 	// 向前合并
// 	while(1)
// 	{
// 		PAGE_ID prevId = span->_pageId - 1;
// 		auto ret = _idSpanMap.find(prevId);

// 		// 前一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		Span* prevSpan = ret->second;
// 		// 前一页的span正在使用，不合并了
// 		if(prevSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1的span，不合并了
// 		if(span->_n + prevSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_pageId = prevSpan->_pageId;
// 		span->_n += prevSpan->_n;

// 		_spanLists[prevSpan->_n].Erase(prevSpan);
// 		delete prevSpan;
// 	}

// 	// 向后合并
// 	while(1)
// 	{
// 		PAGE_ID nextId = span->_pageId + span->_n;
// 		auto ret = _idSpanMap.find(nextId);

// 		// 后一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		Span* nextSpan = ret->second;
// 		// 后一页的span正在使用，不合并了
// 		if(nextSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出大于NPAGES-1的span，不合并了
// 		if(span->_n + nextSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_n += nextSpan->_n;

// 		_spanLists[nextSpan->_n].Erase(nextSpan);
// 		delete nextSpan;
// 	}

// 	_spanLists[span->_n].PushFront(span);
// 	span->_isUse = true;

// 	_idSpanMap[span->_pageId] = span;
// 	_idSpanMap[span->_pageId + span->_n - 1] = span;
// }


// void PageCache::ReleaseSpanToPageCache(Span* span)
// {
// 	assert(span);

// 	// 合并前后页的span组成更大的页，以缓解内存碎片的问题
// 	// 向前合并
// 	while(1)
// 	{
// 		PAGE_ID prevId = span->_pageId - 1;
// 		auto ret = _idSpanMap.find(prevId);

// 		// 前一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		Span* prevSpan = ret->second;
// 		// 前一页的span被使用了，不合并了
// 		if(prevSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了超过NPAGES-1的页，不合并了
// 		if(span->_n + prevSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_pageId = prevSpan->_pageId;
// 		span->_n += prevSpan->_n;

// 		_spanLists[prevSpan->_n].Erase(prevSpan);
// 		delete prevSpan;
// 	}

// 	// 向后合并
// 	while(1)
// 	{
// 		PAGE_ID nextId = span->_pageId + span->_n;
// 		auto ret = _idSpanMap.find(nextId);

// 		// 后一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		Span* nextSpan = ret->second;
// 		// 后一页的span正在被使用，不合并了
// 		if(nextSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了超过NPAGES-1页的span，不合并了
// 		if(span->_n + nextSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_n += nextSpan->_n;

// 		_spanLists[nextSpan->_n].Erase(nextSpan);
// 		delete nextSpan;
// 	}

// 	_spanLists[span->_n].PushFront(span);
// 	span->_isUse = false;

// 	_idSpanMap[span->_pageId] = span;
// 	_idSpanMap[span->_pageId + span->_n - 1] = span;
// }


// // 获取一个K页的span
// Span* PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NPAGES);

// 	// 先查看当前的链表是否有非空的span
// 	if(!_spanLists[k].Empty(0))
// 	{
// 		return _spanLists[k].PopFront();
// 	}

// 	// 走到这说明需要遍历后续的page cache链表桶
// 	for(size_t i = k + 1; i < NPAGES; i++)
// 	{
// 		if(!_spanLists[i].Empty())
// 		{
// 			Span* nSpan = _spanLists[i].PopFront();
// 			Span* kSpan = new Span;

// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n = k;

// 			nSpan->_pageId += k;
// 			nSpan->_n -= k;

// 			_spanLists[nSpan->_n].PushFront(nSpan);

// 			// 建立首尾页号到span的映射，方便page cache合并出更大页的span
// 			_idSpanMap[nSpan->_pageId] = nSpan;
// 			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

// 			// 建立页号到span的映射，方便释放内存对象回来找到对应的span
// 			for(size_t i = 0; i < kSpan->_n; i++)
// 			{
// 				_idSpanMap[kSpan->_pageId + i] = kSpan;
// 			}

// 			return kSpan;
// 		}
// 	}

// 	// 走到这说明需要直接从系统堆中申请大页的span
// 	void* ptr = SystemAlloc(NPAGES - 1);
// 	Span* bigSpan = new Span;

// 	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
// 	bigSpan->_n = NPAGES - 1;

// 	_spanLists[bigSpan->_n].PushFront(bigSpan);

// 	return NewSpan(k);
// }


// // 建立对象到span的映射
// Span* PageCache::MapObjToSpan(void* obj)
// {
// 	assert(obj);

// 	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;
// 	auto ret = _idSpanMap.find(id);

// 	if(ret == _idSpanMap.end())
// 	{
// 		assert(false);
// 		return nullptr;
// 	}
// 	else
// 	{
// 		return ret->second;
// 	}
// }

// void PageCache::ReleaseSpanToPageCache(Span* span)
// {
// 	assert(span);

// 	// 尝试进行前后页的合并组成更大页的span，进而减少内存碎片的浪费
// 	// 向前合并
// 	while(1)
// 	{
// 		PAGE_ID prevId = span->_pageId - 1;
// 		auto ret = _idSpanMap.find(prevId);

// 		// 前面页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		Span* prevSpan = ret->second;
// 		// 前面页的span被使用了，不合并了
// 		if(prevSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1的span，不合并了
// 		if(span->_n + prevSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_pageId = prevSpan->_pageId;
// 		span->_n += prevSpan->_n;

// 		_spanLists[prevSpan->_n].Erase(prevSpan);
// 		delete prevSpan;
// 	}

// 	// 向后合并
// 	while(1)
// 	{
// 		PAGE_ID nextId = span->_pageId + span->_n;
// 		auto ret = _idSpanMap.find(nextId);

// 		// 如果后一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		Span* nextSpan = ret->second;
// 		// 后一页的span别使用了，不合并了
// 		if(nextSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1的span, 不合并了
// 		if(span->_n + nextSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_n += nextSpan->_n;

// 		_spanLists[nextSpan->_n].Erase(nextSpan);
// 		delete nextSpan;
// 	}

// 	_spanLists[span->_n].PushFront(span);
// 	span->_isUse = false;
	
// 	_idSpanMap[span->_pageId] = span;
// 	_idSpanMap[span->_pageId + span->_n - 1] = span;
// }



// // 获取一个K页的span
// Span* PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NPAGES);

// 	// 首先查看该链表中是否有非空的span
// 	if(!_spanLists[k].Empty())
// 	{
// 		return _spanLists[k].PopFront();
// 	}

// 	// 走到这说明需要遍历page cache，找更大页的span，然后切分
// 	for(size_t i = k + 1; i < NPAGES; i++)
// 	{
// 		if(!_spanLists[i].Empty())
// 		{
// 			Span* nSpan = _spanLists[i].PopFront();
// 			Span* kSpan = new Span;

// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n = k;

// 			nSpan->_pageId += k;
// 			nSpan->_n -= k;

// 			_spanLists[nSpan->_n].PushFront(nSpan);

// 			// 记录首尾页号到span的映射，方便page cache合并成更大页的span
// 			_idSpanMap[nSpan->_pageId] = nSpan;
// 			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

// 			// 记录页号到span的映射，方便释放内存时找到对应的span
// 			for(size_t i = 0; i < kSpan->_n; i++)
// 			{
// 				_idSpanMap[kSpan->_pageId + i] = kSpan;
// 			}

// 			return kSpan;
// 		}
// 	}

// 	// 走到这说明需要从page cache中申请内存
// 	void* ptr = SystemAlloc(NPAGES - 1);
// 	Span* bigSpan = new Span;

// 	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
// 	bigSpan->_n = NPAGES - 1;

// 	_spanLists[bigSpan->_n].PushFront(bigSpan);

// 	return NewSpan(k);
// }

// Span* PageCache::MapObjToSpan(void* obj)
// {
// 	assert(obj);

// 	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;
// 	auto ret = _idSpanMap.find(id);

// 	if(ret == _idSpanMap.end())
// 	{
// 		assert(false);
// 		return nullptr;
// 	}
// 	else
// 	{
// 		return ret->second;
// 	}
// }


// void PageCache::ReleaseSpanToPageCache(Span* span)
// {
// 	assert(span);

// 	// 合并前后页的span组成更大页的span，尽量减少内存碎片
// 	// 向前合并
// 	while(1)
// 	{
// 		PAGE_ID prevId = span->_pageId - 1;
// 		auto ret = _idSpanMap.find(prevId);

// 		// 前一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 前一页的span正在使用，不合并了
// 		Span* prevSpan = ret->second;
// 		if(prevSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了更大页的span，不合并了
// 		if(span->_n + prevSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_pageId = prevSpan->_pageId;
// 		span->_n += prevSpan->_n;

// 		_spanLists[prevSpan->_n].Erase(prevSpan);
// 		delete prevSpan;
// 	}

// 	// 向后合并
// 	while(1)
// 	{
// 		PAGE_ID nextId = span->_pageId + span->_n;
// 		auto ret = _idSpanMap.find(nextId);

// 		// 后一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 后一页的span正在被使用，不合并了
// 		Span* nextSpan = ret->second;
// 		if(nextSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了超过NPAGES-1页的span，不合并了
// 		if(span->_n + nextSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_n += nextSpan->_n;

// 		_spanLists[nextSpan->_n].Erase(nextSpan);
// 		delete nextSpan;
// 	}

// 	_spanLists[span->_n].PushFront(span);
// 	span->_isUse = false;

// 	_idSpanMap[span->_pageId] = span;
// 	_idSpanMap[span->_pageId + span->_n - 1] = span;
// }



// // 获取一个K页的span
// Span* PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NPAGES);

// 	// 首先查看当前链表中是否有非空的span
// 	if(!_spanLists[k].Empty())
// 	{
// 		return _spanLists[k].PopFront();
// 	}

// 	// 走到这说明需要遍历page cache获取更大页的span，然后切分
// 	for(size_t i = k + 1; i < NPAGES; i++)
// 	{
// 		if(!_spanLists[i].Empty())
// 		{
// 			Span* nSpan = _spanLists[i].PopFront();
// 			Span* kSpan = new Span;

// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n = k;

// 			nSpan->_pageId += k;
// 			nSpan->_n -= k;

// 			_spanLists[nSpan->_n].PushFront(nSpan);

// 			// 记录首尾页号到span的映射，方便page cache合并成为更大页的是span
// 			_idSpanMap[nSpan->_pageId] = nSpan;
// 			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

// 			// 记录页号到span的映射，方便回收内存时找到对应的span
// 			for(size_t i = 0; i < kSpan->_n; i++)
// 			{
// 				_idSpanMap[kSpan->_pageId + i] = kSpan;
// 			}

// 			return kSpan;
// 		}
// 	}

// 	// 走到这说明需要直接从堆中申请内存
// 	void* ptr = SystemAlloc(NPAGES - 1);
// 	Span* bigSpan = new Span;

// 	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
// 	bigSpan->_n = NPAGES - 1;

// 	return NewSpan(k);
// }

// Span* PageCache::MapObjToSpan(void* obj)
// {
// 	assert(obj);

// 	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;
// 	auto ret = _idSpanMap.find(id);

// 	if(ret == _idSpanMap.end())
// 	{
// 		assert(false);
// 		return nullptr;
// 	}
// 	else
// 	{
// 		return ret->second;
// 	}
// }


// void PageCache::ReleaseSpanToPageCache(Span* span)
// {
// 	assert(span);

// 	// 合并前后页的span徐成更大页的span，从而减少内存碎片
// 	// 向前合并
// 	while(1)
// 	{
// 		PAGE_ID prevId = span->_pageId - 1;
// 		auto ret = _idSpanMap.find(prevId);

// 		// 前一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 前一页的span正在被使用，不合并了
// 		Span* prevSpan = ret->second;
// 		if(prevSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1页的span，不合并了
// 		if(span->_n + prevSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_pageId = prevSpan->_pageId;
// 		span->_n += prevSpan->_n;

// 		_spanLists[prevSpan->_n].Erase(prevSpan);
// 		delete prevSpan;
// 	}

// 	// 向后合并
// 	while(1)
// 	{
// 		PAGE_ID nextId = span->_pageId + span->_n;
// 		auto ret = _idSpanMap.find(nextId);

// 		// 后一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 后一页的span正在被使用，不合并了
// 		Span* nextSpan = ret->second;
// 		if(nextSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1页的span，不合并了
// 		if(span->_n + nextSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_n += nextSpan->_n;

// 		_spanLists[nextSpan->_n].Erase(nextSpan);
// 		delete nextSpan;
// 	}

// 	_spanLists[span->_n].PushFront(span);
// 	span->_isUse = false;

// 	_idSpanMap[span->_pageId] = span;
// 	_idSpanMap[span->_pageId + span->_n - 1] = span;
// }


// // 获取一个K页的span
// Span* PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NPAGES);

// 	// 首先判断当前链表是否有非空的span
// 	if(!_spanLists[k].Empty())
// 	{
// 		return _spanLists[k].PopFront();
// 	}

// 	// 走到这说明需要遍历page cache找更大页的span，然后切开
// 	for(size_t i = k + 1; i < NPAGES; i++)
// 	{
// 		if(!_spanLists[i].Empty())
// 		{
// 			Span* nSpan = _spanLists[i].PopFront();
// 			Span* kSpan = new Span;

// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n = k;

// 			nSpan->_pageId += k;
// 			nSpan->_n -= k;

// 			_spanLists[nSpan->_n].PushFront(nSpan);

// 			// 记录首尾页号到span的映射，方便page cache合并成更大页的span
// 			_idSpanMap[nSpan->_pageId] = nSpan;
// 			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

// 			// 记录页号到span的映射，方便回收内存时找到对应的span
// 			for(size_t i = 0; i < kSpan->_n; i++)
// 			{
// 				_idSpanMap[kSpan->_pageId + i] = kSpan;
// 			}

// 			return kSpan;
// 		}
// 	}

// 	// 走到这说明需要从系统堆中申请大页的span
// 	void* ptr = SystemAlloc(NPAGES - 1);
// 	Span* bigSpan = new Span;

// 	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
// 	bigSpan->_n = NPAGES - 1;

// 	return NewSpan(k);
// }


// // 获取从对象到span的映射
// Span* PageCache::MapObjToSpan(void* obj)
// {
// 	assert(obj);

// 	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;
// 	auto ret = _idSpanMap.find(id);

// 	if(ret == _idSpanMap.end())
// 	{
// 		assert(false);
// 		return nullptr;
// 	}
// 	else
// 	{
// 		return ret->second;
// 	}
// }

// void PageCache::ReleaseSpanToPageCache(Span* span)
// {
// 	assert(span);

// 	// 合并前后页的span组成更大页的span，从而减少内存碎片
// 	// 向前合并
// 	while(1)
// 	{
// 		PAGE_ID prevId = span->_pageId - 1;
// 		auto ret = _idSpanMap.find(prevId);

// 		// 前一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 前一页的span正在被使用，不合并了
// 		Span* prevSpan = ret->second;
// 		if(prevSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了超过NPAGES-1页的span，不合并了
// 		if(span->_n + prevSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_pageId = prevSpan->_pageId;
// 		span->_n += prevSpan->_n;

// 		_spanLists[prevSpan->_n].Erase(prevSpan);
// 		delete prevSpan;
// 	}

// 	// 向后合并
// 	while(1)
// 	{
// 		PAGE_ID nextId = span->_pageId + span->_n;
// 		auto ret = _idSpanMap.find(nextId);

// 		// 后一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 后一页的span正在被使用，不合并了
// 		Span* nextSpan = ret->second;
// 		if(nextSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1页的span，不合并了
// 		if(span->_n + nextSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_n += nextSpan->_n;

// 		_spanLists[nextSpan->_n].Erase(nextSpan);
// 		delete nextSpan;
// 	}

// 	_spanLists[span->_n].PushFront(span);
// 	span->_isUse = false;

// 	_idSpanMap[span->_pageId] = span;
// 	_idSpanMap[span->_pageId + span->_n - 1] = span;

// }


// // 获取一个K页的span
// Span* PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NPAGES);

// 	// 先检查当前链表中是否有空闲的span
// 	if(!_spanLists[k].Empty())
// 	{
// 		return _spanLists[k].PopFront();
// 	}

// 	// 走到这说明需要遍历page cache获取更大页的span，然后切分开

// 	for(size_t i = k + 1; i < NPAGES; i++)
// 	{
// 		if(!_spanLists[i].Empty())
// 		{
// 			Span* nSpan = _spanLists[i].PopFront();
// 			Span* kSpan = new Span;

// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n = k;

// 			nSpan->_pageId += k;
// 			nSpan->_n -= k;

// 			_spanLists[nSpan->_n].PushFront(nSpan);

// 			// 记录首尾页号到span的映射，方便page cache合并成更大页的span
// 			_idSpanMap[nSpan->_pageId] = nSpan;
// 			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

// 			// 记录页号到span的映射，方便central cache释放内存回来时找到对应的span
// 			for(size_t i = 0; i < kSpan->_n; i++)
// 			{
// 				_idSpanMap[kSpan->_pageId + i] = kSpan;
// 			}

// 			return kSpan;
// 		}
// 	}

// 	// 走到这说明需要直接从堆中申请内存
// 	void* ptr = SystemAlloc(NPAGES - 1);
// 	Span* bigSpan = new Span;

// 	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
// 	bigSpan->_n = NPAGES - 1;

// 	return NewSpan(k);
// }



// // 获取从对象到span的映射
// Span* PageCache::MapObjToSpan(void* obj)
// {
// 	assert(obj);

// 	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;
// 	auto ret = _idSpanMap.find(id);

// 	if(ret == _idSpanMap.end())
// 	{
// 		assert(false);
// 		return nullptr;
// 	}
// 	else
// 	{
// 		return ret->second;
// 	}
// }



// void PageCache::ReleaseSpanToPageCache(Span* span)
// {
// 	assert(span);

// 	// 合并前后页的span组成更大页的span，从而减少内存碎片
// 	// 向前合并
// 	while(1)
// 	{
// 		PAGE_ID prevId = span->_pageId - 1;
// 		auto ret = _idSpanMap.find(prevId);

// 		// 前一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 前一页的span正在被使用，不合并了
// 		Span* prevSpan = ret->second;
// 		if(prevSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1页的span，不合并了
// 		if(span->_n + prevSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_pageId = prevSpan->_pageId;
// 		span->_n += prevSpan->_n;

// 		_spanLists[prevSpan->_n].Erase(prevSpan);
// 		delete prevSpan;
// 	}

// 	// 先后合并
// 	while(1)
// 	{
// 		PAGE_ID nextId = span->_pageId + span->_n;
// 		auto ret = _idSpanMap.find(nextId);

// 		// 后一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 后一页的span正在被使用，不合并了
// 		Span* nextSpan = ret->second;
// 		if(nextSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1页的span，不合并了
// 		if(span->_n + nextSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_n += nextSpan->_n;

// 		_spanLists[nextSpan->_n].Erase(nextSpan);
// 		delete nextSpan;
// 	}

// 	_spanLists[span->_n].PushFront(span);
// 	span->_isUse = false;

// 	_idSpanMap[span->_pageId] = span;
// 	_idSpanMap[span->_pageId + span->_n - 1] = span;
// }



// // 获取K页的span
// Span* PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NPAGES);

// 	// 首先检查当前链表中是否有空闲的span
// 	if(!_spanLists[k].Empty())
// 	{
// 		return _spanLists[k].PopFront();
// 	}

// 	// 走到这说明需要遍历page cache获取更大页的span，然后切分
// 	for(size_t i = k + 1; i < NPAGES; i++)
// 	{
// 		if(!_spanLists[i].Empty())
// 		{
// 			Span* nSpan = _spanLists[i].PopFront();
// 			Span* kSpan = new Span;

// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n = k;

// 			nSpan->_pageId += k;
// 			nSpan->_n -= k;

// 			_spanLists[nSpan->_n].PushFront(nSpan);

// 			_idSpanMap[nSpan->_pageId] = nSpan;
// 			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

// 			for(size_t i = 0; i < kSpan->_n; i++)
// 			{
// 				_idSpanMap[kSpan->_pageId + i] = kSpan;
// 			}

// 			return kSpan;
// 		}
// 	}

// 	// 走到这说明需要从系统堆中申请内存
// 	void* ptr = SystemAlloc(NPAGES - 1);
// 	Span* bigSpan = new Span;

// 	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
// 	bigSpan->_n = NPAGES - 1;

// 	_spanLists[bigSpan->_n].PushFront(bigSpan);

// 	return NewSpan(k);
// }

// Span* PageCache::MapObjToSpan(void* obj)
// {
// 	assert(obj);

// 	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;
// 	auto ret = _idSpanMap.find(id);

// 	if(ret == _idSpanMap.end())
// 	{
// 		assert(false);
// 		return nullptr;
// 	}
// 	else
// 	{
// 		return ret->second;
// 	}
// }

// void PageCache::ReleaseSpanToPageCache(Span* span)
// {
// 	assert(span);

// 	// 合并前后页的span组成更大页的span，从而减少内存碎片
// 	// 向前合并
// 	while(1)
// 	{
// 		PAGE_ID prevId = span->_pageId - 1;
// 		auto ret = _idSpanMap.find(prevId);

// 		// 前一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 前一页的span正在被使用，不合并了
// 		Span* prevSpan = ret->second;
// 		if(prevSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1页的span，不合并了
// 		if(span->_n + prevSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_pageId = prevSpan->_pageId;
// 		span->_n += prevSpan->_n;

// 		_spanLists[prevSpan->_n].Erase(prevSpan);
// 		delete prevSpan;
// 	}

// 	// 向后合并
// 	while(1)
// 	{
// 		PAGE_ID nextId = span->_pageId + span->_n;
// 		auto ret = _idSpanMap.find(nextId);

// 		// 后一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 后一页的span正在被使用，不合并了
// 		Span* nextSpan = ret->second;
// 		if(nextSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1的span，不合并了
// 		if(span->_n + nextSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_n += nextSpan->_n;

// 		_spanLists[nextSpan->_n].Erase(nextSpan);
// 		delete nextSpan;
// 	}

// 	_spanLists[span->_n].PushFront(span);
// 	span->_isUse = false;

// 	_idSpanMap[span->_pageId] = span;
// 	_idSpanMap[span->_pageId + span->_n - 1] = span;
// }



// // 获取一个K页的span
// Span* PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NPAGES);

// 	// 先查看当前的链表中是否存在非空的span
// 	if(!_spanLists[k].Empty())
// 	{
// 		return _spanLists[k].PopFront();
// 	}

// 	// 走到这说明需要遍历page cache找到更大页的span，然后切分开来
// 	for(size_t i = k + 1; i < NPAGES; i++)
// 	{
// 		if(!_spanLists[i].Empty())
// 		{
// 			Span* nSpan = _spanLists[i].PopFront();
// 			Span* kSpan = new Span;

// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n = k;

// 			nSpan->_pageId += k;
// 			nSpan->_n -= k;

// 			_spanLists[nSpan->_n].PushFront(nSpan);

// 			_idSpanMap[nSpan->_pageId] = nSpan;
// 			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

// 			for(size_t i = 0; i < kSpan->_n; i++)
// 			{
// 				_idSpanMap[kSpan->_pageId + i] = kSpan;
// 			}

// 			return kSpan;
// 		}
// 	}

// 	// 走到这说明需要直接从系统堆中申请
// 	void* ptr = SystemAlloc(NPAGES - 1);
// 	Span* bigSpan = new Span;

// 	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
// 	bigSpan->_n = NPAGES - 1;

// 	_spanLists[bigSpan->_n].PushFront(bigSpan);
// }


// Span* PageCache::MapObjToSpan(void* obj)
// {
// 	assert(obj);

// 	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;
// 	auto ret = _idSpanMap.find(id);

// 	if(ret == _idSpanMap.end())
// 	{
// 		assert(false);
// 		return nullptr;
// 	}
// 	else
// 	{
// 		return ret->second;
// 	}
// }


// void PageCache::ReleaseSpanToPageCache(Span* span)
// {
// 	assert(span);

// 	// 合并前后页的span组成更大页的span，从而减少内存碎片
// 	// 向前合并
// 	while(1)
// 	{
// 		PAGE_ID prevId = span->_pageId - 1;
// 		auto ret = _idSpanMap.find(prevId);

// 		// 前一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 前一页的span正在使用，不合并了
// 		Span* prevSpan = ret->second;
// 		if(prevSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出超过NPAGES-1页的span，不合并了
// 		if(span->_n + prevSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_pageId = prevSpan->_pageId;
// 		span->_n += prevSpan->_n;

// 		_spanLists[prevSpan->_n].Erase(prevSpan);
// 		delete prevSpan;
// 	}

// 	// 向后合并
// 	while(1)
// 	{
// 		PAGE_ID nextId = span->_pageId + span->_n;
// 		auto ret = _idSpanMap.find(nextId);

// 		// 后一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 后一页的span正在使用，不合并了
// 		Span* nextSpan = ret->second;
// 		if(nextSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1页的span，不合并了
// 		if(span->_n + nextSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_n += nextSpan->_n;

// 		_spanLists[nextSpan->_n].Erase(nextSpan);
// 		delete nextSpan;
// 	}

// 	_spanLists[span->_n].PushFront(span);
// 	span->_isUse = false;

// 	_idSpanMap[span->_pageId] = span;
// 	_idSpanMap[span->_pageId + span->_n - 1] = span;
// }



// // 获取一个K页的span
// Span* PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NPAGES);

// 	// 先查看当前链表中是否存在非空的span
// 	if(!_spanLists[k].Empty())
// 	{
// 		return _spanLists[k].PopFront();
// 	}

// 	// 走到这说明需要遍历page cache找到更大页的span，然后切开
// 	for(size_t i = k + 1; i < NPAGES; i++)
// 	{
// 		if(!_spanLists[i].Empty())
// 		{
// 			Span* nSpan = _spanLists[i].PopFront();
// 			Span* kSpan = new Span;

// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n = k;

// 			nSpan->_pageId += k;
// 			nSpan->_n -= k;

// 			_spanLists[nSpan->_n].PushFront(nSpan);

// 			_idSpanMap[nSpan->_pageId] = nSpan;
// 			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

// 			for(size_t i = 0; i < kSpan->_n; i++)
// 			{
// 				_idSpanMap[kSpan->_pageId + i] = kSpan;
// 			}

// 			return kSpan;
// 		}
// 	}

// 	// 走到这说明需要从系统堆中申请
// 	void* ptr = SystemAlloc(NPAGES - 1);
// 	Span* bigSpan = new Span;

// 	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
// 	bigSpan->_n = NPAGES - 1;

// 	_spanLists[bigSpan->_n].PushFront(bigSpan);

// 	return NewSpan(k);
// }


// // 获取从对象到span的映射
// Span* PageCache::MapObjToSpan(void* start)
// {
// 	assert(start);

// 	PAGE_ID id = (PAGE_ID)start >> PAGE_SHIFT;
// 	auto ret = _idSpanMap.find(id);

// 	if(ret == _idSpanMap.end())
// 	{
// 		assert(false);
// 		return nullptr;
// 	}
// 	else
// 	{
// 		return ret->second;
// 	}
// }


// void PageCache::ReleaseSpanToPageCache(Span* span)
// {
// 	assert(span);

// 	// 尝试进行前后页的合并成更大页的span，从而减少内存碎片
// 	// 向前合并
// 	while(1)
// 	{
// 		PAGE_ID prevId = span->_pageId - 1;
// 		auto ret = _idSpanMap.find(prevId);

// 		// 前一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 前一页的span正在使用，不合并了
// 		Span* prevSpan = ret->second;
// 		if(prevSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1页的span，不合并了
// 		if(span->_n + prevSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_pageId = prevSpan->_pageId;
// 		span->_n += prevSpan->_n;

// 		_spanLists[prevSpan->_n].Erase(prevSpan);
// 		delete prevSpan;
// 	}

// 	// 向后合并
// 	while(1)
// 	{
// 		PAGE_ID nextId = span->_pageId + span->_n;
// 		auto ret = _idSpanMap.find(nextId);
		
// 		// 后一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 后一页的span正在使用，不合并了
// 		Span* nextSpan = ret->second;
// 		if(nextSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1页的span，不合并了
// 		if(span->_n + nextSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_n += nextSpan->_n;

// 		_spanLists[nextSpan->_n].Erase(nextSpan);
// 		delete nextSpan;
// 	}

// 	_spanLists[span->_n].PushFront(span);
// 	span->_isUse = false;

// 	_idSpanMap[span->_pageId] = span;
// 	_idSpanMap[span->_pageId + span->_n - 1] = span;
// }


// // 获取一个K页的span
// Span* PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NPAGES);

// 	// 先判断当前的链表中是否存在非空的span
// 	if(!_spanLists[k].Empty())
// 	{
// 		return _spanLists[k].PopFront();
// 	}

// 	// 走到这说明需要遍历page cache找到更大页的span，然后进行切分
// 	for(size_t i = k + 1; i < NPAGES; i++)
// 	{
// 		if(!_spanLists[i].Empty())
// 		{
// 			Span* nSpan = _spanLists[i].PopFront();
// 			Span* kSpan = new Span;

// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n = k;

// 			nSpan->_pageId += k;
// 			nSpan->_n -= k;

// 			_spanLists[nSpan->_n].PushFront(nSpan);

// 			_idSpanMap[nSpan->_pageId] = nSpan;
// 			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

// 			for(size_t i = 0; i < kSpan->_n; i++)
// 			{
// 				_idSpanMap[kSpan->_pageId + i] = kSpan;
// 			}

// 			return kSpan;
// 		}
// 	}

// 	// 走到这说明需要向系统堆申请大块内存
// 	void* ptr = SystemAlloc(NPAGES - 1);
// 	Span* bigSpan = new Span;

// 	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
// 	bigSpan->_n = NPAGES - 1;

// 	_spanLists[bigSpan->_n].PushFront(span);
// }


// // 获取内存对象到span的映射
// Span* PageCache::MapObjToSpan(void* obj)
// {
// 	assert(obj);

// 	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;
// 	auto ret = _idSpanMap.find(id);

// 	if(ret == _idSpanMap.end())
// 	{
// 		assert(false);
// 		return nullptr;
// 	}
// 	else
// 	{
// 		return ret->second;
// 	}
// }


// void PageCache::ReleaseSpanToPageCache(Span* span)
// {
// 	assert(span);

// 	// 合并前后页的span组成更大页的span，然后进行切分
// 	// 向前合并
// 	while(1)
// 	{
// 		PAGE_ID prevId = span->_pageId - 1;
// 		auto ret = _idSpanMap.find(prevId);

// 		// 前一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 前一页的span正在使用，不合并了
// 		Span* prevSpan = ret->second;
// 		if(prevSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1页的span，不合并了
// 		if(span->_n + prevSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_pageId = prevSpan->_pageId;
// 		span->_n += prevSpan->_n;

// 		_spanLists[prevSpan->_n].Erase(prevSpan);
// 		delete prevSpan;
// 	}

// 	// 向后合并
// 	while(1)
// 	{
// 		PAGE_ID nextId = span->_pageId + span->_n;
// 		auto ret = _idSpanMap.find(nextId);

// 		// 后一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 后一页的span正在使用，不合并了
// 		Span* nextSpan = ret->second;
// 		if(nextSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1页的span，不合并了
// 		if(span->_n + nextSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_n += nextSpan->_n;

// 		_spanLists[nextSpan->_n].Erase(nextSpan);
// 		delete nextSpan;
// 	}

// 	_spanLists[span->_n].PushFront(span);
// 	span->_isUse = false;

// 	_idSpanMap[span->_pageId] = span;
// 	_idSpanMap[span->_pageId + span->_n - 1] = span;
// }



// // 获取K页的span
// Span* PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NPAGES);

// 	// 先查看当前的链表是否存在非空的span
// 	if(!_spanLists[k].Empty())
// 	{
// 		return _spanLists[k].PopFront();
// 	}

// 	// 走到这说明需要遍历page cache找到更大页的span，然后切分
// 	for(size_t i = k + 1; i < NPAGES; i++)
// 	{
// 		if(!_spanLists[i].Empty())
// 		{
// 			Span* nSpan = _spanLists[i].PopFront();
// 			Span* kSpan = new Span;

// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n = k;

// 			nSpan->_pageId += k;
// 			nSpan->_n -= k;

// 			_spanLists[nSpan->_n].PushFront(nSpan);

// 			_idSpanMap[nSpan->_pageId] = nSpan;
// 			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

// 			for(size_t i = 0; i < kSpan->_n; i++)
// 			{
// 				_idSpanMap[kSpan->_pageId + i] = kSpan;
// 			}

// 			return kSpan;
// 		}
// 	}

// 	// 走到这说明需要从系统堆中申请
// 	void* ptr = SystemAlloc(NPAGES - 1);
// 	Span* bigSpan = new Span;

// 	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
// 	bigSpan->_n = NPAGES - 1;

// 	_spanLists[bigSpan->_n].PushFront(bigSpan);
// }


// Span* PageCache::MapObjToSpan(void* obj)
// {
// 	assert(obj);

// 	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;
// 	auto ret = _idSpanMap.find(id);

// 	if(ret == _idSpanMap.end())
// 	{
// 		assert(false);
// 		return nullptr;
// 	}
// 	else
// 	{
// 		return ret->second;
// 	}
// }


// void PageCache::ReleaseSpanToPageCache(Span* span)
// {
// 	assert(span);

// 	// 进行前后页的合并，减少内存碎片
// 	// 向前合并
// 	while(1)
// 	{
// 		PAGE_ID prevId = span->_pageId - 1;
// 		auto ret = _idSpanMap.find(prevId);

// 		// 前一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;;
// 		}

// 		// 前一页的span正在使用，不合并了
// 		Span* prevSpan = ret->second;
// 		if(prevSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1页的span，不合并了
// 		if(span->_n + prevSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_pageId = prevSpan->_pageId;
// 		span->_n += prevSpan->_n;

// 		_spanLists[prevSpan->_n].Erase(prevSpan);
// 		delete prevSpan;
// 	}

// 	// 向后合并
// 	while(1)
// 	{
// 		PAGE_ID nextId = span->_pageId + span->_n;
// 		auto ret = _idSpanMap.find(nextId);

// 		// 后一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 后一页的span正在使用，不合并了
// 		Span* nextSpan = ret->second;
// 		if(nextSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1页的span，不合并了
// 		if(span->_n + nextSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_n += nextSpan->_n;

// 		_spanLists[nextSpan->_n].Erase(nextSpan);
// 		delete nextSpan;
// 	}

// 	_spanLists[span->_n].PushFront(span);
// 	span->_isUse = false;

// 	_idSpanMap[span->_pageId] = span;
// 	_idSpanMap[span->_pageId + span->_n - 1] = span;
// }



// // 获取K页的span
// Span* PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NPAGES);

// 	// 先查看当前的链表中是否存在非空的span
// 	if(!_spanLists[k].Empty())
// 	{
// 		return _spanLists[k].PopFront();
// 	}

// 	// 走到这说明需要遍历page cache找到更大的span，然后切分开来
// 	for(size_t i = k + 1; i < NPAGES; i++)
// 	{
// 		if(!_spanLists[i].Empty())
// 		{
// 			Span* nSpan = _spanLists[i].PopFront();
// 			Span* kSpan = new Span;

// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n = k;

// 			nSpan->_pageId += k;
// 			nSpan->_n -= k;

// 			_spanLists[nSpan->_n].PushFront(nSpan);

// 			_idSpanMap[nSpan->_pageId] = nSpan;
// 			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

// 			for(size_t i = 0; i < kSpan->_n; i++)
// 			{
// 				_idSpanMap[kSpan->_pageId + i] = kSpan;
// 			}

// 			return kSpan;
// 		}

// 		start = next;
// 	}

// 	// 走到这说明需要从系统堆中申请
// 	void* ptr = SystemAlloc(NPAGES - 1);
// 	Span* bigSpan = new Span;

// 	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
// 	bigSpan->_n = NPAGES;

// 	_spanLists[bigSpan->_n].PushFront(bigSpan);

// 	return NewSpan(k);
// }



// Span* PageCache::MapObjToSpan(void* obj)
// {
// 	assert(obj);

// 	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;
// 	auto ret = _idSpanMap.find(id);

// 	if(ret == _idSpanMap.end())
// 	{
// 		assert(false);
// 		return nullptr;
// 	}
// 	else
// 	{
// 		return ret->second;
// 	}
// }


// void PageCache::ReleaseSpanToPageCache(Span* span)
// {
// 	assert(span);

// 	// 合并前后页的span，减少内存碎片
// 	// 向前合并
// 	while(1)
// 	{
// 		PAGE_ID prevId = span->_pageId - 1;
// 		auto ret = _idSpanMap.find(prevId);

// 		// 前一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 前一页的span正在使用，不合并了
// 		Span* prevSpan = ret->second;
// 		if(prevSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1页的span，不合并了
// 		if(span->_n + prevSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_pageId = prevSpan->_pageId;
// 		span->_n += prevSpan->_n;

// 		_spanLists[prevSpan->_n].Erase(prevSpan);
// 		delete prevSpan;
// 	}

// 	// 向后合并
// 	while(1)
// 	{
// 		PAGE_ID nextId = span->_pageId + span->_n;
// 		auto ret = _idSpanMap.find(nextId);

// 		// 后一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 后一页的span正在使用，不合并了
// 		Span* nextSpan = ret->second;
// 		if(nextSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1页的span，不合并了
// 		if(span->_n + nextSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_n += nextSpan->_n;

// 		_spanLists[nextSpan->_n].Erase(nextSpan);
// 		delete nextSpan;
// 	}

// 	_spanLists[span->_n].PushFront(span);
// 	span->_isUse = false;

// 	_idSpanMap[span->_pageId] = span;
// 	_idSpanMap[span->_pageId + span->_n - 1] = span;
// }


// // 获取一个K页的span
// Span* PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NPAGES);

// 	// 先查看当前的链表中是否有非空的span
// 	if(!_spanLists[k].Empty())
// 	{
// 		return _spanLists[k].PopFront();
// 	}

// 	// 走到这说明需要遍历page cache后面更大页的span，然后切分
// 	for(size_t i = k + 1; i < NPAGES; i++)
// 	{
// 		if(_spanLists[i].Empty())
// 		{
// 			Span* nSpan = _spanLists[i].PopFront();
// 			Span* kSpan = new Span;

// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n = k;

// 			nSpan->_pageId += k;
// 			nSpan->_n -= k;

// 			_spanLists[nSpan->_n].PushFront(nSpan);

// 			_idSpanMap[nSpan->_pageId] = nSpan;
// 			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

// 			for(size_t i = 0; i < kSpan->_n; i++)
// 			{
// 				_idSpanMap[kSpan->_pageId + i] = kSpan;
// 			}

// 			return kSpan;
// 		}
// 	}

// 	// 走到这说明需要从系统堆中申请
// 	void* ptr = SystemAlloc(NPAGES - 1);
// 	Span* bigSpan = new Span;

// 	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
// 	bigSpan->_n = NPAGES - 1;

// 	_spanLists[bigSpan->_n].PushFront(bigSpan);

// 	return NewSpan(k);
// }


// Span* PageCache::MapObjToSpan(void* obj)
// {
// 	assert(obj);

// 	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;
// 	auto ret = _idSpanMap.find(id);

// 	if(ret == _idSpanMap.end())
// 	{
// 		assert(false);
// 		return nullptr;
// 	}
// 	else
// 	{
// 		return ret->second;
// 	}
// }


// void PageCache::ReleaseSpanToPageCache(Span* span)
// {
// 	assert(span);

// 	// 合并前后页的span，减少内存碎片
// 	// 向前合并
// 	while(1)
// 	{
// 		PAGE_ID prevId = span->_pageId - 1;
// 		auto ret = _idSpanMap.find(prevId);

// 		// 前一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 前一页的span正在使用，不合并了
// 		Span* prevSpan = ret->second;
// 		if(prevSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1页的span，不合并了
// 		if(span->_n + prevSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_pageId = prevSpan->_pageId;
// 		span->_n += prevSpan->_n;

// 		_spanLists[prevSpan->_n].Erase(prevSpan);
// 		delete prevSpan;
// 	}

// 	// 向后合并
// 	while(1)
// 	{
// 		PAGE_ID nextId = span->_pageId + span->_n;
// 		auto ret = _idSpanMap.find(nextId);

// 		// 后一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 后一页的span正在使用，不合并了
// 		Span* nextSpan = ret->second;
// 		if(nextSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1页的span，不合并了
// 		if(span->_n + nextSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_n += nextSpan->_n;

// 		_spanLists[nextSpan->_n].Erase(nextSpan);
// 		delete nextSpan;
// 	}

// 	_spanLists[span->_n].PushFront(span);
// 	span->_isUse = false;

// 	_idSpanMap[span->_pageId] = span;
// 	_idSpanMap[span->_pageId + span->_n - 1] = span;
// }


// // 获取一个K页的span
// Span* PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NPAGES);

// 	// 先判断当前的链表中是否存在非空的span
// 	if(!_spanLists[k].Empty())
// 	{
// 		return _spanLists[k].PopFront();
// 	}

// 	// 走到这说明需要遍历page cache找到更大页的span，然后切开
// 	for(size_t i = k + 1; i < NPAGES; i++)
// 	{
// 		if(!_spanLists[i].Empty())
// 		{
// 			Span* nSpan = _spanLists[i].PopFront();
// 			Span* kSpan = new Span;

// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n = k;

// 			nSpan->_pageId += k;
// 			nSpan->_n -= k;

// 			_spanLists[nSpan->_n].PushFront(nSpan);

// 			_idSpanMap[nSpan->_pageId] = nSpan;
// 			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

// 			for(size_t i = 0; i < kSpan->_n; i++)
// 			{
// 				_idSpanMap[kSpan->_pageId + i] = kSpan;
// 			}

// 			return kSpan;
// 		}
// 	}

// 	// 走到这说明需要从系统堆中申请
// 	void* ptr = SystemAlloc(NPAGES - 1);
// 	Span* bigSpan = new Span;

// 	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
// 	bigSpan->_n = NPAGES - 1;

// 	_spanLists[bigSpan->_n].PushFront(bigSpan);

// 	return NewSpan(k);
// }


// // 获取一个K页的span
// Span* PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NPAGES);

// 	// 先查看当前的链表是否有非空的span
// 	if(!_spanLists[k].Empty())
// 	{
// 		return _spanLists[k].PopFront();
// 	}

// 	// 走到这说明需要遍历page cache找到更大页的span，然后切分
// 	for(size_t i = k + 1; i < NPAGES; i++)
// 	{
// 		if(!_spanLists[i].Empty())
// 		{
// 			Span* nSpan = _spanLists[i].PopFront();
// 			Span* kSpan = new Span;

// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n = k;

// 			nSpan->_pageId += k;
// 			nSpan->_n -= k;

// 			_spanLists[nSpan->_n].PushFront(nSpan);

// 			_idSpanMap[nSpan->_pageId] = nSpan;
// 			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

// 			for(size_t i = 0; i < kSpan->_n; i++)
// 			{
// 				_idSpanMap[kSpan->_pageId + i] = kSpan;
// 			}

// 			return kSpan;
// 		}
// 	}

// 	// 走到这说明需要从系统堆中申请
// 	void* ptr = SystemAlloc(NPAGES - 1);
// 	Span* bigSpan = new Span;

// 	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
// 	bigSpan->_n = NPAGES - 1;

// 	_spanLists[bigSpan->_n].PushFront(bigSpan);

// 	return NewSpan(k);
// }


// Span* PageCache::MapObjToSpan(void* obj)
// {
// 	assert(obj);

// 	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;
// 	auto ret = _idSpanMap.find(id);

// 	if(ret == _idSpanMap.end())
// 	{
// 		assert(false);
// 		return nullptr;
// 	}
// 	else
// 	{
// 		return ret->second;
// 	}
// }


// void PageCache::ReleaseSpanToPageCache(Span* span)
// {
// 	assert(span);

// 	// 合并前后页的span，从而减少内存碎片
// 	// 向前合并
// 	while(1)
// 	{
// 		PAGE_ID prevId = span->_pageId - 1;
// 		auto ret = _idSpanMap.find(prevId);

// 		// 前一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 前一页的span正在使用，不合并了
// 		Span* prevSpan = ret->second;
// 		if(prevSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NAPGES-1页的span，不合并了
// 		if(span->_n + prevSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_pageId = prevSpan->_pageId;
// 		span->_n += prevSpan->_n;

// 		_spanLists[prevSpan->_n].Erase(prevSpan);
// 		delete prevSpan;
// 	}

// 	// 向后合并
// 	while(1)
// 	{
// 		PAGE_ID nextId = span->_pageId + span->_n;
// 		auto ret = _idSpanMap.find(nextId);

// 		// 后一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 后一页的span正在被使用，不合并了
// 		Span* nextSpan = ret->second;
// 		if(nextSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1页的span，不合并了
// 		if(span->_n + nextSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_n += nextSpan->_n;

// 		_spanLists[nextSpan->_n].Erase(nextSpan);
// 		delete nextSpan;
// 	}

// 	_spanLists[span->_n].PushFront(span);
// 	span->_isUse = fasle;

// 	_idSpanMap[span->_pageId] = span;
// 	_idSpanMap[span->_pageId + span->_n - 1] = span;
// }



// // 获取一个K页的span
// Span* PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NPAGES);

// 	// 首先查看当前的链表中是否存在非空的span
// 	if(!_spanLists[k].Empty())
// 	{
// 		return _spanLists[k].PopFront();
// 	}

// 	// 走到这说明需要遍历page cache找到更大页的span，然后进行切分
// 	for(size_t i = k + 1; i < NPAGES; i++)
// 	{
// 		if(!_spanLists[i].Empty())
// 		{
// 			Span* nSpan = _spanLists[i].PopFront();
// 			Span* kSpan = new Span;

// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n = k;

// 			nSpan->_pageId -= k;
// 			nSpan->_n += k;

// 			_spanLists[nSpan->_n].PushFront(nSpan);

// 			_idSpanMap[nSpan->_pageId] = nSpan;
// 			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

// 			for(size_t i = 0; i < kSpan->_n; i++)
// 			{
// 				_idSpanMap[kSpan->_pageId + i] = kSpan;
// 			}

// 			return kSpan;
// 		}
// 	}

// 	// 走到这说明需要从系统堆中申请内存
// 	void* ptr = SystemAlloc(NPAGES - 1);
// 	Span* bigSpan = new Span;

// 	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
// 	bigSpan->_n = NPAGES - 1;

// 	_spanLists[bigSpan->_n].PushFront(bigSpan);

// 	return NewSpan(k);
// }


// Span* PageCache::MapObjToSpan(void* obj)
// {
// 	assert(obj);

// 	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;
// 	auto ret = _idSpanMap.find(id);

// 	if(ret == _idSpanMap.end())
// 	{
// 		assert(false);
// 		return nullptr;
// 	}
// 	else
// 	{
// 		return ret->second;
// 	}
// }


// void PageCache::ReleaseSpanToPageCache(Span* span)
// {
// 	assert(span);

// 	// 合并前后页的span，从而减少内存碎片
// 	// 向前合并
// 	while(1)
// 	{
// 		PAGE_ID prevId = span->_pageId - 1;
// 		auto ret = _idSpanMap.find(prevId);

// 		// 前一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 前一页的span正在使用，不合并了
// 		Span* prevSpan = ret->second;
// 		if(prevSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1页的span，不合并了
// 		if(span->_n + prevSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_pageId = prevSpan->_pageId;
// 		span->_n += prevSpan->_n;

// 		_spanLists[prevSpan->_n].Erase(prevSpan);
// 		delete prevSpan;
// 	}

// 	// 向后合并
// 	while(1)
// 	{
// 		PAGE_ID nextId = span->_pageId + span->_n;
// 		auto ret = _idSpanMap.find(nextId);

// 		// 后一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 后一页的span正在使用，不合并了
// 		Span* nextSpan = ret->second;
// 		if(nextSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1页的span，不合并了
// 		if(span->_n + nextSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_n += nextSpan->_n;

// 		_spanLists[nextSpan->_n].Erase(nextSpan);
// 		delete nextSpan;
// 	}

// 	_spanLists[span->_n].PushFront(span);
// 	span->_isUse = false;

// 	_idSpanMap[span->_pageId] = span;
// 	_idSpanMap[span->_pageId + span->_n - 1] = span;
// }



// // 获取一个K页的span
// Span* PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NAPGES);

// 	// 先查看当前的链表中是否有非空的span
// 	if(!_spanLists[k].Empty())
// 	{
// 		return _spanLists[k].PopBack();
// 	}

// 	// 走到这说明需要从page cache中获取更大页的span，然后切分
// 	for(size_t i = k + 1; i < NPAGES; i++)
// 	{
// 		if(!_spanLists[i].Empty())
// 		{
// 			Span* nSpan = _spanLists[i].PopBack();
// 			Span* kSpan = new Span;

// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n = k;

// 			nSpan->_pageId += k;
// 			nSpan->_n -= k;

// 			_spanLists[nSpan->_n].PushBack(nSpan);

// 			_idSpanMap[nSpan->_pageId] = nSpan;
// 			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

// 			for(size_t i = 0; i < kSpan->_n; i++)
// 			{
// 				_idSpanMap[kSpan->_pageId + i] = kSpan;
// 			}

// 			return kSpan;
// 		}
// 	}

// 	// 走到这说明需要从系统堆中申请
// 	void* ptr = SystemAlloc(NAPEGS - 1);
// 	Span* bigSpan = new Span;

// 	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
// 	bigSpan->_n = NPAGES - 1;

// 	_spanLists[bigSpan->_n].PushBack(bigSpan);

// 	return NewSpan(k);
// }


// Span* PageCache::MapObjToSpan(void* obj)
// {
// 	assert(obj);

// 	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;
// 	auto ret = _idSpanMap.find(id);

// 	if(ret == _idSpanMap.end())
// 	{
// 		assert(false);
// 		return nullptr;
// 	}
// 	else
// 	{
// 		return ret->second;
// 	}
// }


// void PageCache::ReleaseSpanToPageCache(Span* span)
// {
// 	assert(span);

// 	// 合并前后页相邻的span，从而减少内存碎片
// 	// 向前合并
// 	while(1)
// 	{
// 		PAGE_ID prevId = span->_pageId - 1;
// 		auto ret = _idSpanMap.find(prevId);

// 		// 前一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 前一页的span正在使用，不合并了
// 		Span* prevSpan = ret->second;
// 		if(prevSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NAPGES-1页的span，不合并了
// 		if(span->_n + prevSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_pageId = prevSpan->_pageId;
// 		span->_n += prevSpan->_n;

// 		_spanLists[prevSpan->_n].Erase(prevSpan);
// 		delete prevSpan;
// 	}

// 	// 向后合并
// 	while(1)
// 	{
// 		PAGE_ID nextId = span->_pageId + span->_n;
// 		auto ret = _idSpanMap.find(nextId);

// 		// 后一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 后一页的span正在使用，不合并了
// 		Span* nextSpan = ret->second;
// 		if(nextSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NAPGES-1页的span，不合并了
// 		if(span->_n + nextSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_n += nextSpan->_n;

// 		_spanLists[nextSpan->_n].Erase(nextSpan);
// 		delete nextSpan;
// 	}

// 	_spanLists[span->_n].PushBack(span);
// 	span->_isUse = false;

// 	_idSpanMap[span->_pageId] = span;
// 	_idSpanMap[span->_pageId + span->_n - 1] = span;
// }



// //  获取一个K页的span
// Span* PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NPAGES);

// 	// 判断当前的链表中是否存在非空的span
// 	if(!_spanLists[k].Empty())
// 	{
// 		return _spanLists[k].PopBack();
// 	}

// 	// 走到这说明需要遍历page cache获取更大页的span，然后进行切分
// 	for(size_t i = k + 1; i < NPAGES; i++)
// 	{
// 		if(!_spanLists[i].Empty())
// 		{
// 			Span* nSpan = _spanLists[i].PopBack();
// 			Span* kSpan = new Span;

// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n += nSpan->_n;

// 			nSpan->_pageId += k;
// 			nSpan->_n -= k;

// 			_spanLists[nSpan->_n].PushBack(nSpan);

// 			_idSpanMap[nSpan->_pageId] = nSpan;
// 			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

// 			for(size_t i = 0; i < kSpan->_n; i++)
// 			{
// 				_idSpanMap[kSpan->_pageId + i] = kSpan;
// 			}

// 			return kSpan;
// 		}
// 	}

// 	// 走到这说明需要直接从系统堆中申请
// 	void* ptr = SystemALloc(NAPGES - 1);
// 	Span* bigSpan = new Span;

// 	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
// 	bigSpan->_n = NPAGES - 1;

// 	_spanLists[bigSpan->_n].PushBack(bigSpan);

// 	return NewSpan(k);
// }


// Span* PageCache::MapObjToSpan(void* obj)
// {
// 	assert(obj);

// 	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;
// 	auto ret = _idSpanMap.find(id);

// 	if(ret == _idSpanMap.end())
// 	{
// 		assert(false);
// 		return nullptr;
// 	}
// 	else
// 	{
// 		return ret->second;
// 	}
// }


// void PageCache::ReleaseSpanToPageCache(Span* span)
// {
// 	assert(span);

// 	// 合并前后页的span，减少内存碎片
// 	// 向前合并
// 	while(1)
// 	{
// 		PAGE_ID prevId = span->_pageId - 1;
// 		auto ret = _idSpanMap.find(prevId);

// 		// 前一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 前一页的span正在使用，不合并了
// 		Span* prevSpan = ret->second;
// 		if(prevSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1页的span，不合并了
// 		if(span->_n + prevSpan->_n > NAPGES - 1)
// 		{
// 			break;
// 		}

// 		span->_pageId = prevSpan->_pageId;
// 		span->_n += prevSpan->_n;

// 		_spanLists[prevSpan->_n].Erase(prevSpan);
// 		delete prevSpan;
// 	}

// 	// 向后合并
// 	while(1)
// 	{
// 		PAGE_ID nextId = span->_pageId + span->_n;
// 		auto ret = _idSpanMap.find(nextId);

// 		// 后一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 后一页的span正在使用，不合并了
// 		Span* nextSpan = ret->second;
// 		if(nextSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1页的span，不合并了
// 		if(span->_n + nextSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_n += nextSpan->_n;

// 		_spanLists[nextSpan->_n].Erase(nextSpan);
// 		delete nextSpan;
// 	}

// 	_spanLists[span->_n].PushBack(span);
// 	span->_isUse = true;

// 	_idSpanMap[span->_pageId] = span;
// 	_idSpanMap[span->_pageId + span->_n - 1] = span;
// }




// // 获取一个K页的span
// Span* PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NPAGES);

// 	// 首先判断当前的链表中是否存在非空的span
// 	if(!_spanLists[k].Empty())
// 	{
// 		return _spanLists[k].PopBack();
// 	}

// 	// 走到这说明需要遍历page cache找到更大页的span，然后切分
// 	for(size_t i = k + 1; i < NAPGES; i++)
// 	{
// 		if(_spanLists[i].Empty())
// 		{
// 			Span* nSpan = _spanLists[i].PopBack();
// 			Span* kSpan = new Span;

// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n = k;

// 			nSpan->_pageId += k;
// 			nSpan->_n -= k;

// 			_spanLists[nSpan->_n].PushBack(nSpan);

// 			_idSpanMap[nSpan->_pageId] = nSpan;
// 			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

// 			for(size_t i = 0; i < kSpan->_n; i++)
// 			{
// 				_idSpanMap[kSpan->_pageId + i] = kSpan;
// 			}

// 			return kSpan;
// 		}
// 	}

// 	// 走到这说明需要从系统堆中申请
// 	void* ptr = SystemAlloc(NAPGES - 1);
// 	Span* bigSpan = new Span;

// 	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
// 	bigSpan->_n = NPAGES - 1;

// 	_spanLists[bigSpan->_n].PushBack(bigSpan);

// 	return NewSpan(k);
// }


// Span* PageCache::MapObjToSpan(void* obj)
// {
// 	assert(obj);

// 	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;
// 	auto ret = _idSpanMap.find(id);

// 	if(ret == _idSpanMap.end())
// 	{
// 		assert(false);
// 		return nullptr;
// 	}
// 	else
// 	{
// 		return ret->second;
// 	}
// }


// void PageCache::ReleaseSpanToPageCache(Span* span)
// {
// 	assert(span);

// 	// 合并前后页的span，从而减少内存碎片
// 	// 向前合并
// 	while(1)
// 	{
// 		PAGE_ID prevId = span->_pageId - 1;
// 		auto ret = _idSpanMap.find(prevId);

// 		// 前一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 前一页的span正在使用，不合并了
// 		Span* prevSpan = ret->second;
// 		if(prevSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NPAGES-1页的span，不合并了
// 		if(span->_n + prevSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_pageId = prevSpan->_pageId;
// 		span->_n += prevSpan->_n;

// 		_spanLists[prevSpan->_n].Erase(prevSpan);
// 		delete prevSpan;
// 	}

// 	// 向后合并
// 	while(1)
// 	{
// 		PAGE_ID nextId = span->_pageId + span->_n;
// 		auto ret = _idSpanMap.find(nextId);

// 		// 后一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 后一页的span正在使用，不合并了
// 		Span* nextSpan = ret->second;
// 		if(nextSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NAPGES-1页的span，不合并了
// 		if(span->_n + nextSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_n += nextSpan->_n;

// 		_spanLists[nextSpan->_n].Erase(nextSpan);
// 		delete nextSpan;
// 	}

// 	_spanLists[span->_n].PushBack(span);
// 	span->_isUse = false;

// 	_idSpanMap[span->_pageId] = span;
// 	_idSpanMap[span->_pageId + span->_n - 1] = span;
// }


// // 获取一个K页的span
// Span* PageCache::NewSpan(size_t k)
// {
// 	assert(k > 0 && k < NPAGES);

// 	// 先判断当前的链表中是否存在非空的span
// 	if(!_spanLists[k].Empty())
// 	{
// 		return _spanLists[k].PopBack();
// 	}

// 	// 走到这说明需要遍历page cache找到更大页的span，然后切分
// 	for(size_t i = k + 1; i < NPAGES; i++)
// 	{
// 		if(!_spanLists[i].Empty())
// 		{
// 			Span* nSpan = _spanLists[i].PopBack();
// 			Span* kSpan = new Span;

// 			kSpan->_pageId = nSpan->_pageId;
// 			kSpan->_n = k;

// 			nSpan->_pageId += k;
// 			nSpan->_n -= k;

// 			_spanLists[nSpan->_n].PushBack(nSpan);

// 			_idSpanMap[nSpan->_pageId] = nSpan;
// 			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

// 			for(size_t i = 0; i < kSpan->_n; i++)
// 			{
// 				_idSpanMap[kSpan->_pageId + i] = kSpan;
// 			}

// 			return kSpan;
// 		}
// 	}

// 	// 走到这说明需要从系统堆中申请大页的span
// 	void* ptr = SystemAlloc(NPAGES - 1);
// 	Span* bigSpan = new Span;

// 	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
// 	bigSpan->_n = NPAGES - 1;

// 	_spanLists[bigSpan->_n].PushBack(bigSpan);

// 	return NewSpan(k);
// }


// Span* PageCache::MapObjToSpan(void* obj)
// {
// 	assert(obj);

// 	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;
// 	auto ret = _idSpanMap.find(id);

// 	if(ret == _idSpanMap.end())
// 	{
// 		assert(false);
// 		return nullptr;
// 	}
// 	else
// 	{
// 		return ret->second;
// 	}
// }


// void PageCache::ReleaseSpanToPageCache(Span* span)
// {
// 	assert(span);

// 	// 合并前后页的span，从而减少内存碎片
// 	// 向前合并
// 	while(1)
// 	{
// 		PAGE_ID prevId = span->_pageId - 1;
// 		auto ret = _idSpanMap.find(prevId);

// 		// 前一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 前一页的span正在使用，不合并了
// 		Span* prevSpan = ret->second;
// 		if(prevSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并出了大于NAPGES-1页的span，不合并了
// 		if(span->_n + prevSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_pageId = prevSpan->_pageId;
// 		span->_n += prevSpan->_n;

// 		_spanLists[prevSpan->_n].Erase(prevSpan);
// 		delete prevSpan;
// 	}

// 	// 向后合并
// 	while(1)
// 	{
// 		PAGE_ID nextId = span->_pageId + span->_n;
// 		auto ret = _idSpanMap.find(nextId);

// 		// 后一页的span不存在，不合并了
// 		if(ret == _idSpanMap.end())
// 		{
// 			break;
// 		}

// 		// 后一页的span正在使用，不合并了
// 		Span* nextSpan = ret->second;
// 		if(nextSpan->_isUse == true)
// 		{
// 			break;
// 		}

// 		// 合并超过了NPAGES-1页的span，不合并了
// 		if(span->_n + nextSpan->_n > NPAGES - 1)
// 		{
// 			break;
// 		}

// 		span->_n += nextSpan->_n;

// 		_spanLists[nextSpan->_n].Erase(nextSpan);
// 		delete nextSpan;
// 	}

// 	_spanLists[span->_n].PushBack(span);
// 	span->_isUse = false;

// 	_idSpanMap[span->_pageId] = span;
// 	_idSpanMap[span->_pageId + span->_n - 1] = span;
// }


// 获取一个K页的span
Span* PageCache::NewSpan(size_t k)
{
	assert(k > 0 && k < NPAGES);

	// 首先判断当前的链表中是否有非空的span
	if(!_spanLists[k].Empty())
	{
		return _spanLists[k].PopFront();
	}

	// 走到这说明需要遍历page cache找到更大页的span，然后进行切分
	for(size_t i = k + 1; i < NPAGES; i++)
	{
		if(!_spanLists[i].Empty())
		{
			Span* nSpan = _spanLists[i].PopFront();
			Span* kSpan = new Span;

			kSpan->_pageId = nSpan->_pageId;
			kSpan->_n = k;

			nSpan->_pageId += k;
			nSpan->_n -= k;

			_spanLists[nSpan->_n].PushFront(nSpan);

			_idSpanMap[nSpan->_pageId] = nSpan;
			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

			for(size_t i = 0; i < kSpan->_n; i++)
			{
				_idSpanMap[kSpan->_pageId + i] = kSpan;
			}

			return kSpan;
		}
	}

	// 走到这说明需要从系统堆中申请
	void* ptr = SystemAlloc(NPAGES - 1);
	Span* bigSpan = new Span;

	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
	bigSpan->_n = NPAGES - 1;

	_spanLists[bigSpan->_n].PushFront(bigSpan);

	return NewSpan(k);
}


Span* PageCache::MapObjToSpan(void* obj)
{
	assert(obj);

	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;
	auto ret = _idSpanMap.find(id);

	if(ret == _idSpanMap.end())
	{
		assert(false);
		return nullptr;
	}
	else
	{
		return ret->second;
	}
}


void PageCache::ReleaseSpanToPageCache(Span* span)
{
	assert(span);

	// 合并前后页的span，减少内存碎片
	// 向前合并
	while(1)
	{
		Span* prevId = span->_pageId - 1;
		auto ret = _idSpanMap.find(id);
 
		// 前一页的span不存在，不合并了
		if(ret == _idSpanMap.end())
		{
			break;
		}

		// 前一页的span正在使用，不合并了
		Span* prevSpan = ret->second;
		if(prevSpan->_isUse == true)
		{
			break;
		}

		// 合并出了大于NPAGES-1页的span，不合并了
		if(span->_n + prevSpan->_n > NPAGES - 1)
		{
			break;
		}

		span->_pageId = prevSpan->_pageId;
		span->_n += prevSpan->_n;

		_spanLists[prevSpan->_n].Erase(prevSpan);
		delete prevSpan;
	}

	// 向后合并
	while(1)
	{
		PAGE_ID nextId = span->_pageId + span->_n;
		auto ret = _idSpanMap.find(nextId);

		// 后一页的span不存在，不合并了
		if(ret == _idSpanMap.end())
		{
			break;
		}

		// 后一页的span正在使用，不合并了
		Span* nextSpan = ret->second;
		if(nextSpan->_isUse == true)
		{
			break;
		}

		// 合并出了大于NPAGES-1页的span，不合并了
		if(span->_n + nextSpan->_n > NPAGES - 1)
		{
			break;
		}

		span->_n += nextSpan->_n;

		_spanLists[nextSpan->_n].Erase(nextSpan);
		delete nextSpan;
	}

	_spanLists[span->_n].PushFront(span);
	span->_isUse = false;

	_idSpanMap[span->_pageId] = span;
	_idSpanMap[span->_pageId + span->_n - 1] = span;
}





Span* PageCache::NewSpan(size_t k)
{
	assert(k > 0 && k < NPAGES);

	if(!_spanLists[k].Empty())
	{
		return _spanLists[k].PopFront();
	}

	for(int i = k + 1; i < NPAGES; i++)
	{
		if(!_spanLists[i].Empty())
		{
			Span* nSpan = _spanLists[i].PopFront();
			Span* kSpan = new Span;

			kSpan->_pageId = nSpan->_pageId;
			kSpan->_n = k; 

			nSpan->_pageId += k;
			nSpan->_n -= k;

			_spanLists[nSpan->_n].PushFront(nSpan);

			_idSpanMap[nSpan->_pageId] = nSpan;
			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

			for(int i = 0; i < kSpan->_n; i++)
			{
				_idSpanMap[kSpan->_pageId + i] = kSpan;
			}

			return kSpan;
		}
	}

	void* obj = SystemAlloc(NPAGES - 1);
	Span* bigSpan = new Span;

	bigSpan->_pageId = (PAGE_ID)obj >> PAGE_SHIFT;
	bigSpan->_n = NPAGES - 1;

	_spanLists[bigSpan->_n].PushFront(bigSpan);

	return NewSpan(k);
}


Span* PageCache::MapObjToSpan(void* obj)
{
	assert(obj);

	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;
	auto ret = _idSpanMap.find(id);

	if(ret == _idSpanMap.end())
	{
		assert(false);
		return nullptr;
	}
	else
	{
		return ret->second;
	}
}


void PageCache::ReleaseSpanToPageCache(Span* span)
{
	assert(span);

	// 合并前后页的span，减少内存碎片
	// 向前合并
	while(1)
	{
		PAGE_ID prevId = span->_pageId - 1;
		auto ret = _idSpanMap.find(prevId);

		// 前一页的span不存在，不合并了
		if(ret == _idSpanMap.end())
		{
			break;
		}

		// 前一页的span正在使用，不合并了
		Span* prevSpan = ret->second;
		if(prevSpan->_isUse == true)
		{
			break;
		}

		// 合并出了大于NPAGES-1页的span，不合并了
		if(span->_n + prevSpan->_n > NPGAES - 1)
		{
			break;
		}

		span->_pageId = prevSpan->_pageId;
		span->_n += prevSpan->_n;

		_spanLists[prevSpan->_n].Erase(prevSpan);
		delete prevSpan;
	}

	// 向后合并
	while(1)
	{
		PAGE_ID nextId = span->_pageId + span->_n;
		auto ret = _idSpanMap.find(nextId);

		// 后一页的span不存在，不合并了
		if(ret == _idSpanMap.end)
		{
			break;
		}

		// 后一页的span正在使用，不合并了
		Span* nextSpan = ret->second;
		if(nextSpan->_isUse == true)
		{
			break;
		}

		// 合并出了大于NPAGES-1页的span，不合并了
		if(span->_n + nextSpan->_n > NPAGES - 1)
		{
			break;
		}

		span->_n += nextSpan->_n;

		_spanLists[nextSpan->_n].Erase(nextSpan);
		delete nextSpan;
	}

	_spanLists[span->_n].PushFront(span);
	span->_isUse = true;

	_idSpanMap[span->_pageId] = span;
	_idSpanMap[span->_pageId + span->_n - 1] = span;
}


// 获取一个K页的span
Span* PageCache::NewSpan(size_t k)
{
    assert(k < NPAGES);

    // 首先判断当前的链表中是否有非空的span
    if(!_spanLists[k].Empty())
    {
        return _spanLists[k].PopFront();
    }

    // 走到这说明需要遍历找到更大页的span，然后进行切分
    for(int i = k + 1; i < NPAGES; i++)
    {
        if(!_spanLists[i].Empty())
        {
            Span* nSpan = _spanLists[i].PopFront();
            Span* kSpan = new Span;

            kSpan->_pageId = nSpan->_pageId;
            kSpan->_n = k; 

            nSpan->_pageId += k;
            nSpan->_n -= k;

            _spanLists[nSpan->_n].PushFront(nSpan);

            _idSpanMap[nSpan->_pageId] = nSpan;
            _idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

            for(size_t j = 0; j < kSpan->_n; j++)
            {
                _idSpanMap[kSpan->_pageId + j] = kSpan;
            }

            return kSpan;
        }
    }

    // 走到这说明需要从系统堆中申请
    void* obj = SystemAlloc(NPAGES - 1);
    Span* bigSpan = new Span;

    bigSpan->_pageId = (PAGE_ID)obj >> PAGE_SHIFT;
    bigSpan->_n = NPAGES - 1;

    return PageCache::GetInstance()->NewSpan(k);
}


// 建立从页号到span的映射
Span* PageCache::MapObjToSpan(void* obj)
{
    assert(obj);

    PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;
    auto ret = _idSpanMap.find(id);

    if(ret == _idSpanMap.end())
    {
        assert(false);
        return nullptr;
    }
    else
    {
        return ret->second;
    }
}


// 合并前后页相邻的span，组成更大的页，较少内存碎片
void PageCache::ReleaseSpanToPageCache(Span* span)
{
    assert(span);

    // 向前合并
    while(1)
    {
        // 前一页的span不存在，不合并了
        PAGE_ID prevId = span->_pageId - 1;
        auto ret = _idSpanMap.find(prevId);
        if(ret == _idSpanMap.end())
        {
            break;
        }

        // 前一页的span正在被使用，不合并了
        Span* prevSpan = ret->second;
        if(prevSpan->_isUse == true)
        {
            break;
        }

        // 合并出了大于NPAGES-1页的span，不合并了
        if(span->_n + prevSpan->_n > NPAGES - 1)
        {
            break;
        }

        span->_pageId = prevSpan->_pageId;
        span->_n += prevSpan->_n;

        _spanLists[prevSpan->_n].Erase(prevSpan);
        delete prevSpan;        
    }

    // 向后合并
    while(1)
    {
        // 后一页的span不存在，不合并了
        PAGE_ID nextId = span->_pageId + span->_n;
        auto ret = _idSpanMap.find(nextId);
        if(ret == _idSpanMap.end())
        {
            break;
        }

        // 后一页的span正在被使用，不合并了
        Span* nextSpan = ret->second;
        if(nextSpan->_isUse == true)
        {
            break;
        }

        // 合并出了大于NPAGES-1页的span，不合并了
        if(span->_n + nextSpan->_n > NPAGES - 1)
        {
            break;
        }

        span->_n += nextSpan->_n;

        _spanLists[nextSpan->_n].Erase(nextSpan);
        delete nextSpan;
    }

    _spanLists[span->_n].PushFront(span);
    span->_isUse = false;

    _idSpanMap[span->_pageId] = span;
    _idSpanMap[span->_pageId + span->_n - 1] = span;
}


